Race in rpi_clear_remote?

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 345

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk

the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +2 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 
 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 13 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +2 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 
 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

Quoted 86 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +8 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 
 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.
+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 5 lines

ksrc/nucleus/shadow.c +1 -0

+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 

Quoted 87 lines · Philippe Gerum

Quoted 86 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +8 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 
 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.
+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+

Quoted 8 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 5 lines

ksrc/nucleus/shadow.c +1 -0

+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

Jan

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Quoted 170 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

Jan

Quoted 170 lines · Jan Kiszka

Quoted 169 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 4 lines

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

No, it can't, that is the crux of the matter, well, at least, this should not be possible if the basic assumptions are preserved (have a look at the rpi_clear_remote() callers, the target thread may not migrate or be scheduled in linux-wise, or exit RPI via rpi_pop() during the call -- all places where the rpi backlink may be cleared). Only a caller operating from the local CPU should be allowed to alter the RPI state of threads linked to the RPI slot of that same CPU.

rpi_clear_remote() is not even an exception to this, since it alters a remote RPI slot, but for a thread which does run on the local CPU.

Quoted 4 lines

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

My patch attempts fixing the core issue, not just plugging one of its bad outcomes.

Again, the point is not to pretend that your patch is wrong, and it surely "plugs" one issue we have due to rpi_next(). The point is to make sure that all issues are covered, by fixing the usage of rpi_next(), or find another way to fix what rpi_next() was supposed to fix in the first place.

Quoted 192 lines · Philippe Gerum

Quoted 170 lines · Jan Kiszka

Quoted 169 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 4 lines

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

No, it can't, that is the crux of the matter, well, at least, this should not be possible if the basic assumptions are preserved (have a look at the rpi_clear_remote() callers, the target thread may not migrate or be scheduled in linux-wise, or exit RPI via rpi_pop() during the call -- all places where the rpi backlink may be cleared). Only a caller operating from the local CPU should be allowed to alter the RPI state of threads linked to the RPI slot of that same CPU.

rpi_clear_remote() is not even an exception to this, since it alters a remote RPI slot, but for a thread which does run on the local CPU.

Quoted 4 lines

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

Quoted 8 lines

My patch attempts fixing the core issue, not just plugging one of its bad outcomes.

Again, the point is not to pretend that your patch is wrong, and it surely "plugs" one issue we have due to rpi_next(). The point is to make sure that all issues are covered, by fixing the usage of rpi_next(), or find another way to fix what rpi_next() was supposed to fix in the first place.

So, if you are right, we could (in theory) replace rpilock with local IRQ disabling? That would be the proof from me that it doesn't matter to test thread->rpi outside the lock.

Jan

Quoted 199 lines · Jan Kiszka

Quoted 198 lines · Philippe Gerum

Quoted 170 lines · Jan Kiszka

Quoted 169 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 4 lines

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

No, it can't, that is the crux of the matter, well, at least, this should not be possible if the basic assumptions are preserved (have a look at the rpi_clear_remote() callers, the target thread may not migrate or be scheduled in linux-wise, or exit RPI via rpi_pop() during the call -- all places where the rpi backlink may be cleared). Only a caller operating from the local CPU should be allowed to alter the RPI state of threads linked to the RPI slot of that same CPU.

rpi_clear_remote() is not even an exception to this, since it alters a remote RPI slot, but for a thread which does run on the local CPU.

Quoted 4 lines

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

My patch attempts fixing the core issue, not just plugging one of its bad outcomes.

Again, the point is not to pretend that your patch is wrong, and it surely "plugs" one issue we have due to rpi_next(). The point is to make sure that all issues are covered, by fixing the usage of rpi_next(), or find another way to fix what rpi_next() was supposed to fix in the first place.

Quoted 3 lines

So, if you are right, we could (in theory) replace rpilock with local IRQ disabling? That would be the proof from me that it doesn't matter to test thread->rpi outside the lock.

Noo, you did not get it yet. The rpilock is protecting the per-cpu RPI queues, NOT thread->rpi.

Quoted 204 lines · Philippe Gerum

Quoted 202 lines · Jan Kiszka

Quoted 190 lines · Philippe Gerum

Quoted 170 lines · Jan Kiszka

Quoted 169 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 4 lines

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

No, it can't, that is the crux of the matter, well, at least, this should not be possible if the basic assumptions are preserved (have a look at the rpi_clear_remote() callers, the target thread may not migrate or be scheduled in linux-wise, or exit RPI via rpi_pop() during the call -- all places where the rpi backlink may be cleared). Only a caller operating from the local CPU should be allowed to alter the RPI state of threads linked to the RPI slot of that same CPU.

rpi_clear_remote() is not even an exception to this, since it alters a remote RPI slot, but for a thread which does run on the local CPU.

Quoted 4 lines

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

Quoted 8 lines

My patch attempts fixing the core issue, not just plugging one of its bad outcomes.

Again, the point is not to pretend that your patch is wrong, and it surely "plugs" one issue we have due to rpi_next(). The point is to make sure that all issues are covered, by fixing the usage of rpi_next(), or find another way to fix what rpi_next() was supposed to fix in the first place.

So, if you are right, we could (in theory) replace rpilock with local IRQ disabling? That would be the proof from me that it doesn't matter to test thread->rpi outside the lock.

Quoted 2 lines

Noo, you did not get it yet. The rpilock is protecting the per-cpu RPI queues, NOT thread->rpi.

So linking a thread to an RPI queue and setting its ->rpi are not always related?

Jan

Quoted 201 lines · Jan Kiszka

Quoted 200 lines · Philippe Gerum

Quoted 199 lines · Jan Kiszka

Quoted 198 lines · Philippe Gerum

Quoted 170 lines · Jan Kiszka

Quoted 169 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it /seems/ like thread->rpi is invalid. Looking at the code, I wonder if this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread) {
...

        rpi = thread->rpi;
        if (unlikely(rpi == NULL))
                return;

        xnlock_get_irqsave(&rpi->rpilock, s);

        /*
         * The RPI slot - if present - is always valid, and won't
         * change since the thread is resuming on this CPU and cannot
         * migrate under our feet. We may grab the remote slot lock
         * now.
         */
        xnsched_pop_rpi(thread);
        thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but we check for it without any protection? Sounds racy. I think 'thread' is not only pointing to the current thread but could refer to a foreign one as well, right? Don't we need this:

ksrc/nucleus/shadow.c +0 -0

index 872c37f..1f995d6 100644
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 12 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 342

Quoted 9 lines

ksrc/nucleus/shadow.c +6 -0

+	/* Re-check under lock, someone may have cleared rpi by now. */
+	if (unlikely(thread->rpi == NULL)) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
 	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 4 lines

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

No, it can't, that is the crux of the matter, well, at least, this should not be possible if the basic assumptions are preserved (have a look at the rpi_clear_remote() callers, the target thread may not migrate or be scheduled in linux-wise, or exit RPI via rpi_pop() during the call -- all places where the rpi backlink may be cleared). Only a caller operating from the local CPU should be allowed to alter the RPI state of threads linked to the RPI slot of that same CPU.

rpi_clear_remote() is not even an exception to this, since it alters a remote RPI slot, but for a thread which does run on the local CPU.

Quoted 4 lines

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

My patch attempts fixing the core issue, not just plugging one of its bad outcomes.

Again, the point is not to pretend that your patch is wrong, and it surely "plugs" one issue we have due to rpi_next(). The point is to make sure that all issues are covered, by fixing the usage of rpi_next(), or find another way to fix what rpi_next() was supposed to fix in the first place.

Quoted 7 lines

Quoted 5 lines

Quoted 3 lines

So, if you are right, we could (in theory) replace rpilock with local IRQ disabling? That would be the proof from me that it doesn't matter to test thread->rpi outside the lock.

Noo, you did not get it yet. The rpilock is protecting the per-cpu RPI queues, NOT thread->rpi.

So linking a thread to an RPI queue and setting its ->rpi are not always related?

Exactly. Normally, a remote CPU should not be allowed to compete with another one for updating the rpi backlink of a thread it does NOT own, meaning not linked to the local scheduler.

My understanding is that rpi_next() is deliberately breaking that rule when called from rpi_clear_remote() for a non-local scheduler, therefore altering rpi backlinks of threads which do NOT belong to the local scheduler.

Who is wrong then? Well, I tend to think that rpi_next() should not be called in the only cross-CPU context we have, namely rpi_clear_remote(). In that very particular case, where we own the target thread, and we want to complete its recent migration to our local CPU.

This is why I was insisting on the notion of calling context for all rpi* calls, with respect to what threads may be touched by a given CPU.

But, I am now worried by xnshadow_rpi_check(), which - by calling rpi_next() instead of simply peeking at the RPI queue head - introduces a potential race wrt the rpi backlink, when we deal with rpi_clear_remote() on the _same_ CPU.

Quoted 210 lines · Philippe Gerum

Quoted 201 lines · Jan Kiszka

Quoted 200 lines · Philippe Gerum

Quoted 199 lines · Jan Kiszka

Quoted 198 lines · Philippe Gerum

Quoted 170 lines · Jan Kiszka

Quoted 169 lines · Philippe Gerum

Quoted 147 lines · Jan Kiszka

Quoted 78 lines · Philippe Gerum

Quoted 77 lines · Jan Kiszka

Quoted 41 lines · Jan Kiszka

Quoted 40 lines · Jan Kiszka

Hi,

I'm meditating over an oops in rpi_clear_remote. NULL pointer deref, it
/seems/ like thread->rpi is invalid. Looking at the code, I wonder if
this could explain the bug:

static void rpi_clear_remote(struct xnthread *thread)
{
...
rpi = thread->rpi;
if (unlikely(rpi == NULL))
return;

xnlock_get_irqsave(&rpi->rpilock, s);

/*
* The RPI slot - if present - is always valid, and won't
* change since the thread is resuming on this CPU and cannot
* migrate under our feet. We may grab the remote slot lock
* now.
*/
xnsched_pop_rpi(thread);
thread->rpi = NULL;

...

So we deref (xnsched_pop_rpi) and clear thread->rpi under rpilock, but
we check for it without any protection? Sounds racy. I think 'thread' is
not only pointing to the current thread but could refer to a foreign one
as well, right? Don't we need this:

diff --git a/ksrc/nucleus/shadow.c b/ksrc/nucleus/shadow.c
index 872c37f..1f995d6 100644
--- a/ksrc/nucleus/shadow.c
+++ b/ksrc/nucleus/shadow.c
@@ -331,6 +331,12 @@ static void rpi_clear_remote(struct xnthread *thread)

xnlock_get_irqsave(&rpi->rpilock, s);

Quoted 12 lines

Quoted 9 lines

+ /* Re-check under lock, someone may have cleared rpi by now. */
+ if (unlikely(thread->rpi == NULL)) {
+ xnlock_put_irqrestore(&rpi->rpilock, s);
+ return;
+ }
+
/*
* The RPI slot - if present - is always valid, and won't
* change since the thread is resuming on this CPU and cannot

Another worry: Can thread->rpi become != rpi without being NULL? Or can we really only race for clearance here?

I think so now, therefore I'm proposing this:

----------->

Most RPI services work on the current task or the one to be scheduled in next, thus are naturally serialized. But rpi_next is not as it can walk the chain of RPI requests for a CPU independently. In that case, clearing RPI via rpi_clear_remote can race with rpi_next, and if the former loses after checking thread->rpi for NULL, we will dereference a NULL pointer in xnsched_pop_rpi().

Signed-off-by Jan Kiszka <[email protected]>

---
 ksrc/nucleus/shadow.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

ksrc/nucleus/shadow.c +0 -0

index 872c37f..cf7c08f 100644
@@ -332,6 +332,15 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnlock_get_irqsave(&rpi->rpilock, s);
 

Quoted 16 lines

Quoted 4 lines

ksrc/nucleus/shadow.c +2 -0

 	/*
+	 * Re-check under lock. Someone may have invoked rpi_next and cleared
+	 * rpi by now.

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 346

Quoted 10 lines

ksrc/nucleus/shadow.c +7 -0

+	 */
+	if (unlikely(!rpi_p(thread))) {
+		xnlock_put_irqrestore(&rpi->rpilock, s);
+		return;
+	}
+
+	/*
 	 * The RPI slot - if present - is always valid, and won't
 	 * change since the thread is resuming on this CPU and cannot
 	 * migrate under our feet. We may grab the remote slot lock

The suggested patch papers over the actual issue, which is that rpi_clear_remote() may not invoke rpi_next(), because it may only affect

I don't think that in our case rpi_clear_remote called rpi_next and therefore crashed. It should rather have been the scenario of both running in parallel on different CPUs, the former on behalf of a migrated shadow that wants to clear its remainders on the remote CPU, the latter on that CPU, picking a new top RPI after some other shadow was removed from the queue. Is this a possible scenario, and would your patch cover it?

Quoted 44 lines

the RPI state of the argument thread which must be a local one, and not that of any random thread that happens to be linked to the remote RPI queue.

By calling rpi_next(), rpi_clear_remote() shoots itself in the foot, allowing a concurrent invocation of itself on a remote CPU, to fiddle with the rpi backlink of a thread which is not active on the local/per-cpu Xenomai scheduler instance, which is the point where things start to hit the crapper.

Now, unless I can't even synchronize the couple of neurons I have left at this hour, the following patch should better fix the issue, because it restores the two basic rules that apply to the whole RPI machinery, namely:

- rpi_* calls may only alter the contents of the local scheduler's RPI queue, with the notable exception of rpi_clear_remote() which may remove the given _local_ thread only, from a remote RPI slot.

- rpi_* calls may only change the RPI state of threads which are controlled by the local Xenomai scheduler instance, except rpi_push() when called for setting up the RPI state of an emerging thread, in which case this is a no-conflict zone.

That breakage was introduced in the early 2.5.1 timeframe, so 2.4.x should be immune from this particular bug.

ksrc/nucleus/shadow.c +6 -1

index 872c37f..1397ed1 100644
@@ -340,7 +340,12 @@ static void rpi_clear_remote(struct xnthread *thread)
 	xnsched_pop_rpi(thread);
 	thread->rpi = NULL;
 
-	if (rpi_next(rpi, s) == NULL)
+	/*
+	 * If the remote RPI queue was emptied, prepare for kicking
+	 * xnshadow_rpi_check() on the relevant CPU to demote the root
+	 * thread priority there.
+	 */
+	if (xnsched_peek_rpi(rpi) == NULL) /* No rpi_next() here. */
 		rcpu = xnsched_cpu(rpi);
 

Quoted 9 lines

ksrc/nucleus/shadow.c static void rpi_clear_remote(struct xnthread *thread) · line 351

Quoted 3 lines

ksrc/nucleus/shadow.c +0 -0

 	xnlock_put_irqrestore(&rpi->rpilock, s);

I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code. However, the fact that thread->rpi is now again only checked outside its protecting lock leaves me with a very bad feeling...

My point is that we should not have to protect a section of code which may never conflict in any case, by design; we will likely agree that sprinkling locks everywhere to get a warm and fuzzy feeling is no solution, it's actually a significant source of regression.

The idea, behind keeping most rpi_* operations applicable to locally scheduled threads, is to introduce such a design, even when remote RPI slots are involved. thread->sched == xnpod_current_sched() for each rpi_*(sched, ...) calls is what is important in this logic. Another original assumption was that no RPI updates could be done in interrupt context, which is now wrong due to the change in xnshadow_rpi_check().

Quoted 4 lines

Quoted 2 lines

In short: we have to make sure that rpi_next() does not break the basic assumptions of the RPI core, first.

Please check my scenario again: My concern is that a thread can be queued for a short while on a remote sched,

No, it can't, that is the crux of the matter, well, at least, this should not be possible if the basic assumptions are preserved (have a look at the rpi_clear_remote() callers, the target thread may not migrate or be scheduled in linux-wise, or exit RPI via rpi_pop() during the call -- all places where the rpi backlink may be cleared). Only a caller operating from the local CPU should be allowed to alter the RPI state of threads linked to the RPI slot of that same CPU.

rpi_clear_remote() is not even an exception to this, since it alters a remote RPI slot, but for a thread which does run on the local CPU.

Quoted 4 lines

and while that is the case,
it can be manipulated (/wrt ->rpi) _concurrently_ (as we do not hold the remote rpilock all the time). I'm quite sure now that your patch does not change this.

My patch attempts fixing the core issue, not just plugging one of its bad outcomes.

Again, the point is not to pretend that your patch is wrong, and it surely "plugs" one issue we have due to rpi_next(). The point is to make sure that all issues are covered, by fixing the usage of rpi_next(), or find another way to fix what rpi_next() was supposed to fix in the first place.

Quoted 7 lines

Quoted 5 lines

Quoted 3 lines

So, if you are right, we could (in theory) replace rpilock with local IRQ disabling? That would be the proof from me that it doesn't matter to test thread->rpi outside the lock.

Noo, you did not get it yet. The rpilock is protecting the per-cpu RPI queues, NOT thread->rpi.

So linking a thread to an RPI queue and setting its ->rpi are not always related?

Quoted 8 lines

Exactly. Normally, a remote CPU should not be allowed to compete with another one for updating the rpi backlink of a thread it does NOT own, meaning not linked to the local scheduler.

My understanding is that rpi_next() is deliberately breaking that rule when called from rpi_clear_remote() for a non-local scheduler, therefore altering rpi backlinks of threads which do NOT belong to the local scheduler.

Just dug out the backtrace again: Where we saw the crash was (likely - lots of inline functions) in the chain schedule_event -> rpi_switch -> rpi_migrate -> rpi_clear_remote. To my understanding, this clear takes place on the CPU that is the target of the just migrated Linux task. At that point, isn't the task's shadow no longer linked to the original CPU's RPI queue? And if that remote CPU now calls rpi_next e.g. via rpi_pop, doesn't that step cause a clearance as well, thus races with the one we started via rpi_migrate?

Even if I'm wrong on the above, the conditions for manipulating thread->rpi should be documented or even checked (i.e. when setting thread->rpi, thread->sched must equal the local sched - right?).

Quoted 6 lines

Who is wrong then? Well, I tend to think that rpi_next() should not be called in the only cross-CPU context we have, namely rpi_clear_remote(). In that very particular case, where we own the target thread, and we want to complete its recent migration to our local CPU.

Quoted 7 lines

This is why I was insisting on the notion of calling context for all rpi* calls, with respect to what threads may be touched by a given CPU.

But, I am now worried by xnshadow_rpi_check(), which - by calling rpi_next() instead of simply peeking at the RPI queue head - introduces a potential race wrt the rpi backlink, when we deal with rpi_clear_remote() on the _same_ CPU.

OK, then we have at least one reason to not trust thread->rpi unless we hold rpilock. That's my whole point.

BTW, the pattern I suggested is a fairly common one in the kernel due to all its complex (because fine-grained) locking. And that I thought I had to introduce raised my worries about RPI locking noticeably. :-/

Don't you think that, quoting yourself:

"I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code"

does not fit that well with any kind of strong assertion made later on the same topic, not backed by facts?

So, I'm suggesting that we move on, and end this discussion in a positive manner, i.e. by fixing this code. I hear your concerns, like I always do, and I'm trying to find a solution that does not paper over another issue. I guess we should be able to settle on this.

I pushed two patches in my for-upstream queue, with lengthy comments to explain what they do and why this is needed:

http://git.xenomai.org/?p=xenomai-rpm.git;a=commit;h=ac5c739dabcb14334c2e390a9e3064f11f97283c
http://git.xenomai.org/?p=xenomai-rpm.git;a=commit;h=d3242401b8e1cf2c28822f801b681194243b4394

- the first patch is a plain revert of the commit introducing rpi_next(), which caused the bug you observed in SMP mode, and that your patch plugged successfully.

- the second patch is the proper fix for the issue rpi_next() tried to address.

Could you please try them, and report whether this also fixes the issue for you? In the meantime, I will be analyzing the RPI code once again, to check whether your patch still covers a possible case, or not.

Quoted 6 lines · Philippe Gerum

Don't you think that, quoting yourself:

"I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code"

Quoted 2 lines

does not fit that well with any kind of strong assertion made later on the same topic, not backed by facts?

See, as long as you do not directly explain why my concerns on this naturally racy construct were not valid (I brought up quite a few concrete questions),

I couldn't help raising them over and over again.
This has, in fact, nothing to do with understanding the RPI code in all its details. It's about reviewing basic patterns of it. But now that the critical bit is gone, I'm surely no longer concerned. :)

Quoted 19 lines

So, I'm suggesting that we move on, and end this discussion in a positive manner, i.e. by fixing this code. I hear your concerns, like I always do, and I'm trying to find a solution that does not paper over another issue. I guess we should be able to settle on this.

I pushed two patches in my for-upstream queue, with lengthy comments to explain what they do and why this is needed:

http://git.xenomai.org/?p=xenomai-rpm.git;a=commit;h=ac5c739dabcb14334c2e390a9e3064f11f97283c
http://git.xenomai.org/?p=xenomai-rpm.git;a=commit;h=d3242401b8e1cf2c28822f801b681194243b4394

- the first patch is a plain revert of the commit introducing rpi_next(), which caused the bug you observed in SMP mode, and that your patch plugged successfully.

- the second patch is the proper fix for the issue rpi_next() tried to address.

Quoted 3 lines

Could you please try them, and report whether this also fixes the issue for you? In the meantime, I will be analyzing the RPI code once again, to check whether your patch still covers a possible case, or not.

I will try my best, but the issue showed up only once in countless application runs. We will role out the patches at the next chance (we already had to push my workaround as we need to deliver the fastsynch fix, so it may take a while).

Jan

Quoted 9 lines · Jan Kiszka

Quoted 8 lines · Philippe Gerum

Don't you think that, quoting yourself:

"I have to confess, I do not understand how the patch may relate to our crash. But that's because I still only have a semi-understanding of this frightening complex RPI code"

does not fit that well with any kind of strong assertion made later on the same topic, not backed by facts?

Quoted 3 lines

See, as long as you do not directly explain why my concerns on this naturally racy construct were not valid (I brought up quite a few concrete questions),

Which were answered. And you seem to consider that a construct is racy by design without taking care of understanding why they could be perfectly valid in the proper context. This is what I was pointing out, all time long.