[PATCH] user_intr: a lock to protect main_intr_queue

[Junling Ma]

1. The queue manipulated by two threads, the registration server and the intr_thread, so we need a lock to protect it.
2. To initialize the lock, we introduce a irq_init function in i386/i386/irq.[ch] and call it in device/device_init.c

---
device/device_init.c | 3 ++-
device/intr.c | 26 ++++++++++++++++++++------
device/intr.h | 6 ++++--
i386/i386/irq.c | 16 ++++++++++++----
i386/i386/irq.h | 2 ++
5 files changed, 40 insertions(+), 13 deletions(-)

diff --git a/device/device_init.c b/device/device_init.c
index 794186ee..4e5109ff 100644
--- a/device/device_init.c
+++ b/device/device_init.c
@@ -41,7 +41,7 @@
#include <device/ds_routines.h>
#include <device/net_io.h>
#include <device/chario.h>
-
+#include <machine/irq.h>

ipc_port_t master_device_port;

@@ -60,6 +60,7 @@ device_service_create(void)
net_io_init();
device_pager_init();
chario_init();
+ irq_init();

(void) kernel_thread(kernel_task, io_done_thread, 0);
(void) kernel_thread(kernel_task, net_thread, 0);
diff --git a/device/intr.c b/device/intr.c
index fbb9f495..705dc1c6 100644
--- a/device/intr.c
+++ b/device/intr.c
@@ -23,18 +23,31 @@

#ifndef MACH_XEN

-queue_head_t main_intr_queue;
+extern struct irqdev irqtab;
+#define main_intr_queue irqtab.intr_queue
static boolean_t deliver_intr (int id, ipc_port_t dst_port);

+#define PROTECT(lock, critical_section) \
+{\
+ simple_lock(&lock);\
+ critical_section;\
+ simple_unlock(&lock);\
+}
+
static user_intr_t *
search_intr (struct irqdev *dev, ipc_port_t dst_port)
{
user_intr_t *e;
- queue_iterate (dev->intr_queue, e, user_intr_t *, chain)
+ simple_lock(&dev->lock);
+ queue_iterate (&dev->intr_queue, e, user_intr_t *, chain)
{
if (e->dst_port == dst_port)
- return e;
+ {
+ simple_unlock(&dev->lock);
+ return e;
+ }
}
+ simple_unlock(&dev->lock);
return NULL;
}

@@ -64,7 +77,7 @@ irq_acknowledge (ipc_port_t receive_port)
if (irqtab.irqdev_ack)
(*(irqtab.irqdev_ack)) (&irqtab, e->id);

- __enable_irq (irqtab.irq[e->id]);
+ PROTECT(irqtab.lock, __enable_irq (irqtab.irq[e->id]));

return D_SUCCESS;
}
@@ -139,7 +152,7 @@ insert_intr_entry (struct irqdev *dev, int id, ipc_port_t dst_port)
new->interrupts = 0;
new->n_unacked = 0;

- queue_enter (dev->intr_queue, new, user_intr_t *, chain);
+ PROTECT(dev->lock, queue_enter (&dev->intr_queue, new, user_intr_t *, chain));
out:
splx (s);
if (free)
@@ -153,7 +166,6 @@ intr_thread (void)
user_intr_t *e;
int id;
ipc_port_t dst_port;
- queue_init (&main_intr_queue);

for (;;)
{
@@ -163,6 +175,7 @@ intr_thread (void)
spl_t s = splhigh ();

/* Check for aborted processes */
+ simple_lock(&irqtab.lock);
queue_iterate (&main_intr_queue, e, user_intr_t *, chain)
{
if ((!e->dst_port || e->dst_port->ip_references == 1) && e->n_unacked)
@@ -231,6 +244,7 @@ intr_thread (void)
s = splhigh ();
}
}
+ simple_unlock(&irqtab.lock);
splx (s);
thread_block (NULL);
}
diff --git a/device/intr.h b/device/intr.h
index cd3e0bce..54ddb331 100644
--- a/device/intr.h
+++ b/device/intr.h
@@ -42,14 +42,14 @@ struct irqdev {
char *name;
void (*irqdev_ack)(struct irqdev *dev, int id);

- queue_head_t *intr_queue;
+ queue_head_t intr_queue;
+ decl_simple_lock_data(, lock);/* a lock to protect the intr_queue */
int tot_num_intr; /* Total number of unprocessed interrupts */

/* Machine dependent */
irq_t irq[NINTR];
};

-extern queue_head_t main_intr_queue;
extern int install_user_intr_handler (struct irqdev *dev, int id, unsigned long flags, user_intr_t *e);
extern int deliver_user_intr (struct irqdev *dev, int id, user_intr_t *e);
extern user_intr_t *insert_intr_entry (struct irqdev *dev, int id, ipc_port_t receive_port);
@@ -57,6 +57,8 @@ extern user_intr_t *insert_intr_entry (struct irqdev *dev, int id, ipc_port_t re
void intr_thread (void);
kern_return_t irq_acknowledge (ipc_port_t receive_port);

+void irq_init(void);
+
#endif /* MACH_XEN */

#endif
diff --git a/i386/i386/irq.c b/i386/i386/irq.c
index 35681191..4ef1c43f 100644
--- a/i386/i386/irq.c
+++ b/i386/i386/irq.c
@@ -60,8 +60,16 @@ __enable_irq (irq_t irq_nr)
splx(s);
}

-struct irqdev irqtab = {
- "irq", irq_eoi, &main_intr_queue, 0,
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
-};
+struct irqdev irqtab;
+
+void irq_init()
+{
+ irqtab.name = "irq";
+ irqtab.irqdev_ack = irq_eoi;
+ queue_init (&irqtab.intr_queue);
+ simple_lock_init(&irqtab.lock);
+ irqtab.tot_num_intr = 0;
+ for (int i = 0; i < NINTR; ++i)
+ irqtab.irq[i] = i;
+}

diff --git a/i386/i386/irq.h b/i386/i386/irq.h
index d48a8e92..1ca105ef 100644
--- a/i386/i386/irq.h
+++ b/i386/i386/irq.h
@@ -22,6 +22,8 @@ typedef unsigned int irq_t;
void __enable_irq (irq_t irq);
void __disable_irq (irq_t irq);

+void irq_init();
+
extern struct irqdev irqtab;

#endif
--
2.28.0.rc1

[Samuel Thibault]

Junling Ma, le dim. 02 août 2020 21:04:24 -0700, a ecrit:

> -struct irqdev irqtab = {
> - "irq", irq_eoi, &main_intr_queue, 0,
> - {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
> -};
> +struct irqdev irqtab;
> +
> +void irq_init()
> +{
> + irqtab.name = "irq";
> + irqtab.irqdev_ack = irq_eoi;

> + irqtab.tot_num_intr = 0;

Err, why doing this dynamically at initialization time while we can do
it statically once for good at compile-time?

> + queue_init (&irqtab.intr_queue);
> + simple_lock_init(&irqtab.lock);

Please rather introduce initializers in queue.h and lock.h, so that
again it's initialized statically. Yes, for the queue you will need to
pass the initializer the address of the structure field, that is fine
and expected for such a macro.

> + for (int i = 0; i < NINTR; ++i)
> + irqtab.irq[i] = i;
> +}

I'd still rather see it initialized statically.

> +#define PROTECT(lock, critical_section) \
> +{\
> + simple_lock(&lock);\
> + critical_section;\
> + simple_unlock(&lock);\
> +}

As mentioned on IRC, please make this a SIMPLE_LOCKED macro in lock.h
itself, it can be useful beyond this file.

> static user_intr_t *
> search_intr (struct irqdev *dev, ipc_port_t dst_port)
> {
> user_intr_t *e;
> - queue_iterate (dev->intr_queue, e, user_intr_t *, chain)
> + simple_lock(&dev->lock);
> + queue_iterate (&dev->intr_queue, e, user_intr_t *, chain)
> {
> if (e->dst_port == dst_port)
> - return e;
> + {
> + simple_unlock(&dev->lock);
> + return e;
> + }
> }
> + simple_unlock(&dev->lock);
> return NULL;
> }

I believe you want to make the *caller* lock, here. Otherwise another
CPU could be removing the entry you have just found. That's actually the
point of splhigh/splx in the callers.

> @@ -64,7 +77,7 @@ irq_acknowledge (ipc_port_t receive_port)
> if (irqtab.irqdev_ack)
> (*(irqtab.irqdev_ack)) (&irqtab, e->id);
>
> - __enable_irq (irqtab.irq[e->id]);
> + PROTECT(irqtab.lock, __enable_irq (irqtab.irq[e->id]));

I don't think we need a lock here. Yes, we need to protect
__enable_irq's stuff, but I don't think it's device/intr.c's duty to do
this. __enable_irq actually already has some of it, we'd just need to
add a simple lock in addition (and possibly introduce a simple+splhigh
helper to do this)

> @@ -163,6 +175,7 @@ intr_thread (void)
> spl_t s = splhigh ();
>
> /* Check for aborted processes */
> + simple_lock(&irqtab.lock);
> queue_iterate (&main_intr_queue, e, user_intr_t *, chain)

Please move the lock above the "Check" comment. Otherwise we'd think we
lock only for the aborted check, while we lock also for the interrupt
check.

> {
> if ((!e->dst_port || e->dst_port->ip_references == 1) && e->n_unacked)
> @@ -231,6 +244,7 @@ intr_thread (void)
> s = splhigh ();
> }
> }
> + simple_unlock(&irqtab.lock);

We probably want to unlock earlier than this, before we call
deliver_intr. Otherwise we keep the lock busy while doing the delivery.
Even worse with the kfree call. Again, basically follow the existing
splhigh/splx, it already provides the uniprocessor concerns which
already have the problem of interrupts happening concurrently.

Note: after the deliver_intr call, we will want to break as well, in
order to restart iterating over the queue again, otherwise the current
entry may have disappeared and you'd iterate in the space.

Samuel

[Samuel Thibault]

Oh, btw, in queue_intr you also need to take the simple_lock which
modifying the entry values.

Samuel

[Junling Ma]

Hi Samual,

> On Aug 4, 2020, at 4:51 PM, Samuel Thibault <samuel....@gnu.org> wrote:
>
> Junling Ma, le dim. 02 août 2020 21:04:24 -0700, a ecrit:
>> -struct irqdev irqtab = {
>> - "irq", irq_eoi, &main_intr_queue, 0,
>> - {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
>> -};
>> +struct irqdev irqtab;
>> +
>> +void irq_init()
>> +{
>> + irqtab.name = "irq";
>> + irqtab.irqdev_ack = irq_eoi;
>> + irqtab.tot_num_intr = 0;
>
> Err, why doing this dynamically at initialization time while we can do
> it statically once for good at compile-time?
>
>> + queue_init (&irqtab.intr_queue);
>> + simple_lock_init(&irqtab.lock);
>
> Please rather introduce initializers in queue.h and lock.h, so that
> again it's initialized statically. Yes, for the queue you will need to
> pass the initializer the address of the structure field, that is fine
> and expected for such a macro.

Yes that makes sense.

>
>> + for (int i = 0; i < NINTR; ++i)
>> + irqtab.irq[i] = i;
>> +}
>
> I'd still rather see it initialized statically.

In the future, we may have LAPIC and IOAPIC, so the array may not be determined at compile time For the simple ASPIC, there would be no problem to statically init it.

>> +#define PROTECT(lock, critical_section) \
>> +{\
>> + simple_lock(&lock);\
>> + critical_section;\
>> + simple_unlock(&lock);\
>> +}
>
> As mentioned on IRC, please make this a SIMPLE_LOCKED macro in lock.h
> itself, it can be useful beyond this file.

Sure.

>> static user_intr_t *
>> search_intr (struct irqdev *dev, ipc_port_t dst_port)
>> {
>> user_intr_t *e;
>> - queue_iterate (dev->intr_queue, e, user_intr_t *, chain)
>> + simple_lock(&dev->lock);
>> + queue_iterate (&dev->intr_queue, e, user_intr_t *, chain)
>> {
>> if (e->dst_port == dst_port)
>> - return e;
>> + {
>> + simple_unlock(&dev->lock);
>> + return e;
>> + }
>> }
>> + simple_unlock(&dev->lock);
>> return NULL;
>> }
>
> I believe you want to make the *caller* lock, here. Otherwise another
> CPU could be removing the entry you have just found. That's actually the
> point of splhigh/splx in the callers.

I think splhigh/splx disable interrupts, but the interrupt handler will not touch the queue any more, only the intr_thread does. Wouldn’t a simple lock be sufficient?

>> @@ -64,7 +77,7 @@ irq_acknowledge (ipc_port_t receive_port)
>> if (irqtab.irqdev_ack)
>> (*(irqtab.irqdev_ack)) (&irqtab, e->id);
>>
>> - __enable_irq (irqtab.irq[e->id]);
>> + PROTECT(irqtab.lock, __enable_irq (irqtab.irq[e->id]));
>
> I don't think we need a lock here. Yes, we need to protect
> __enable_irq's stuff, but I don't think it's device/intr.c's duty to do
> this. __enable_irq actually already has some of it, we'd just need to
> add a simple lock in addition (and possibly introduce a simple+splhigh
> helper to do this)

You are right. Actually, we probably do not need to lock at all, These ack calls are serialized at the msg server, so they cannot mess each other. The intr_thread does not enable irq unless the port is dead, in which case there would be no ack calls.

>> @@ -163,6 +175,7 @@ intr_thread (void)
>> spl_t s = splhigh ();
>>
>> /* Check for aborted processes */
>> + simple_lock(&irqtab.lock);
>> queue_iterate (&main_intr_queue, e, user_intr_t *, chain)
>
> Please move the lock above the "Check" comment. Otherwise we'd think we
> lock only for the aborted check, while we lock also for the interrupt
> check.

Ok.

>> {
>> if ((!e->dst_port || e->dst_port->ip_references == 1) && e->n_unacked)
>> @@ -231,6 +244,7 @@ intr_thread (void)
>> s = splhigh ();
>> }
>> }
>> + simple_unlock(&irqtab.lock);
>
> We probably want to unlock earlier than this, before we call
> deliver_intr. Otherwise we keep the lock busy while doing the delivery.
> Even worse with the kfree call. Again, basically follow the existing
> splhigh/splx, it already provides the uniprocessor concerns which
> already have the problem of interrupts happening concurrently.

Yes we only need to protect the dead port deletion part to prevent device registratio from appending to the queue while we delete here. The delivery loop should be safe without locking.

> Note: after the deliver_intr call, we will want to break as well, in
> order to restart iterating over the queue again, otherwise the current
> entry may have disappeared and you'd iterate in the space.

I guess we should simple check if the port is dead before delivery. Ah, that is why the old code marks for freeing, and free after the delivery loop. I didn’t;t get that. So, we check if the port is dead, and if so, we free the port and set it to NULL, and continue. After the delivery loop finishes, we unregister and free all the dead user_intr_t.

Junling

[Junling Ma]

In the next patch, we disallow deliver_user_intr from touching the queue, so we do not need to lock it. In fact, by doing that, we prevent interrupts from pulling the rug under our feet, so there is no need to do splhigh/splx in irq_acknowledge and intr_thread.

Junling

[Samuel Thibault]

Junling Ma, le mar. 04 août 2020 17:08:03 -0700, a ecrit:

> >> static user_intr_t *
> >> search_intr (struct irqdev *dev, ipc_port_t dst_port)
> >> {
> >> user_intr_t *e;
> >> - queue_iterate (dev->intr_queue, e, user_intr_t *, chain)
> >> + simple_lock(&dev->lock);
> >> + queue_iterate (&dev->intr_queue, e, user_intr_t *, chain)
> >> {
> >> if (e->dst_port == dst_port)
> >> - return e;
> >> + {
> >> + simple_unlock(&dev->lock);
> >> + return e;
> >> + }
> >> }
> >> + simple_unlock(&dev->lock);
> >> return NULL;
> >> }
> >
> > I believe you want to make the *caller* lock, here. Otherwise another
> > CPU could be removing the entry you have just found. That's actually the
> > point of splhigh/splx in the callers.
>
> I think splhigh/splx disable interrupts, but the interrupt handler will not touch the queue any more, only the intr_thread does. Wouldn’t a simple lock be sufficient?

You not only have the interrupt handler, but also other processors doing
stuff.

Note: simple_lock is optimized to void in uni-processor builds. simple
locks are there only to handle multi-processor cases. They just cannot
protect at all against an interrupt, that's what splhigh is for.

> >> @@ -64,7 +77,7 @@ irq_acknowledge (ipc_port_t receive_port)
> >> if (irqtab.irqdev_ack)
> >> (*(irqtab.irqdev_ack)) (&irqtab, e->id);
> >>
> >> - __enable_irq (irqtab.irq[e->id]);
> >> + PROTECT(irqtab.lock, __enable_irq (irqtab.irq[e->id]));
> >
> > I don't think we need a lock here. Yes, we need to protect
> > __enable_irq's stuff, but I don't think it's device/intr.c's duty to do
> > this. __enable_irq actually already has some of it, we'd just need to
> > add a simple lock in addition (and possibly introduce a simple+splhigh
> > helper to do this)
>
> You are right. Actually, we probably do not need to lock at all, These ack calls are serialized at the msg server, so they cannot mess each other. The intr_thread does not enable irq unless the port is dead, in which case there would be no ack calls.

I don't think we want to base safety over the precise behavior of other
code, but only over simple conventions that are properly documented.

> >> if ((!e->dst_port || e->dst_port->ip_references == 1) && e->n_unacked)
> >> @@ -231,6 +244,7 @@ intr_thread (void)
> >> s = splhigh ();
> >> }
> >> }
> >> + simple_unlock(&irqtab.lock);
> >
> > We probably want to unlock earlier than this, before we call
> > deliver_intr. Otherwise we keep the lock busy while doing the delivery.
> > Even worse with the kfree call. Again, basically follow the existing
> > splhigh/splx, it already provides the uniprocessor concerns which
> > already have the problem of interrupts happening concurrently.
>
> Yes we only need to protect the dead port deletion part to prevent device registratio from appending to the queue while we delete here. The delivery loop should be safe without locking.

No, it's not completely safe, you need to protect against other
processors doing other stuff.

Samuel

[Samuel Thibault]

Junling Ma, le mar. 04 août 2020 17:11:06 -0700, a ecrit:
> In the next patch, we disallow deliver_user_intr from touching the queue, so we do not need to lock it.

We don't want separate patch to depend on each other. Each patch should
by its own just *work* so we can test all of them one after the other
separately.

Please read about git bisect.

Yes, we need to protect ++ / -- against other processors
reading/writing to them.

Samuel

[Junling Ma]

Please bear with me as I am slow here. The interrupt handler does not touch the queue. It works on the user_intr_t pointer. So we use simple_lock to protect again other threads, but we do not need splhigh/splx to protect us against the interrupt handler.

>>>> @@ -64,7 +77,7 @@ irq_acknowledge (ipc_port_t receive_port)
>>>> if (irqtab.irqdev_ack)
>>>> (*(irqtab.irqdev_ack)) (&irqtab, e->id);
>>>>
>>>> - __enable_irq (irqtab.irq[e->id]);
>>>> + PROTECT(irqtab.lock, __enable_irq (irqtab.irq[e->id]));
>>>
>>> I don't think we need a lock here. Yes, we need to protect
>>> __enable_irq's stuff, but I don't think it's device/intr.c's duty to do
>>> this. __enable_irq actually already has some of it, we'd just need to
>>> add a simple lock in addition (and possibly introduce a simple+splhigh
>>> helper to do this)
>>
>> You are right. Actually, we probably do not need to lock at all, These ack calls are serialized at the msg server, so they cannot mess each other. The intr_thread does not enable irq unless the port is dead, in which case there would be no ack calls.
>
> I don't think we want to base safety over the precise behavior of other
> code, but only over simple conventions that are properly documented.

We can protect __enable_irq and __disable_irq with a lock. But that is tricky, because __disable_irq is called in the interrupt handler. Another thread holding a lock while interrupt happens causes a deadlock.

>
>>>> if ((!e->dst_port || e->dst_port->ip_references == 1) && e->n_unacked)
>>>> @@ -231,6 +244,7 @@ intr_thread (void)
>>>> s = splhigh ();
>>>> }
>>>> }
>>>> + simple_unlock(&irqtab.lock);
>>>
>>> We probably want to unlock earlier than this, before we call
>>> deliver_intr. Otherwise we keep the lock busy while doing the delivery.
>>> Even worse with the kfree call. Again, basically follow the existing
>>> splhigh/splx, it already provides the uniprocessor concerns which
>>> already have the problem of interrupts happening concurrently.
>>
>> Yes we only need to protect the dead port deletion part to prevent device registratio from appending to the queue while we delete here. The delivery loop should be safe without locking.
>
> No, it's not completely safe, you need to protect against other
> processors doing other stuff.

What other stuff though? The queue is is only manipulation by the intr_thread and registration. No other threads or interrupts mess with the queue.

Junling

[Samuel Thibault]

Junling Ma, le mar. 04 août 2020 17:59:57 -0700, a ecrit:

There's a misunderstanding. When I wrote "That's actually the point
of splhigh/splx in the callers." I meant that it is the point of
splhigh/splx being in the caller, and not in the callee. I am not
saying splhigh/splx should necessarily be kept. I am saying that
simple_lock/unlock should be in the caller, not the callee, for the same
reason why splhigh/splx was in the caller and not in the callee.

> >>>> @@ -64,7 +77,7 @@ irq_acknowledge (ipc_port_t receive_port)
> >>>> if (irqtab.irqdev_ack)
> >>>> (*(irqtab.irqdev_ack)) (&irqtab, e->id);
> >>>>
> >>>> - __enable_irq (irqtab.irq[e->id]);
> >>>> + PROTECT(irqtab.lock, __enable_irq (irqtab.irq[e->id]));
> >>>
> >>> I don't think we need a lock here. Yes, we need to protect
> >>> __enable_irq's stuff, but I don't think it's device/intr.c's duty to do
> >>> this. __enable_irq actually already has some of it, we'd just need to
> >>> add a simple lock in addition (and possibly introduce a simple+splhigh
> >>> helper to do this)
> >>
> >> You are right. Actually, we probably do not need to lock at all, These ack calls are serialized at the msg server, so they cannot mess each other. The intr_thread does not enable irq unless the port is dead, in which case there would be no ack calls.
> >
> > I don't think we want to base safety over the precise behavior of other
> > code, but only over simple conventions that are properly documented.
>
> We can protect __enable_irq and __disable_irq with a lock. But that is tricky, because __disable_irq is called in the interrupt handler. Another thread holding a lock while interrupt happens causes a deadlock.

That is why you cannot use only a simple lock, but also splhigh/splx.
Please read the LDD https://lwn.net/Kernel/LDD3/ and more precisely its
chapter on concurrency https://static.lwn.net/images/pdf/LDD3/ch05.pdf
and the spin_lock_irq helper that does both the equivalent of
simple_lock *and* splhigh.

> >>>> if ((!e->dst_port || e->dst_port->ip_references == 1) && e->n_unacked)
> >>>> @@ -231,6 +244,7 @@ intr_thread (void)
> >>>> s = splhigh ();
> >>>> }
> >>>> }
> >>>> + simple_unlock(&irqtab.lock);
> >>>
> >>> We probably want to unlock earlier than this, before we call
> >>> deliver_intr. Otherwise we keep the lock busy while doing the delivery.
> >>> Even worse with the kfree call. Again, basically follow the existing
> >>> splhigh/splx, it already provides the uniprocessor concerns which
> >>> already have the problem of interrupts happening concurrently.
> >>
> >> Yes we only need to protect the dead port deletion part to prevent device registratio from appending to the queue while we delete here. The delivery loop should be safe without locking.
> >
> > No, it's not completely safe, you need to protect against other
> > processors doing other stuff.
>
> What other stuff though?

That can be anything. Registering a new irq, killing a process, etc. If
you expect only intr_thread to be removing entries from the queue, then
add it as a fat comment on the queue declaration, and then yes, you can
start assuming it, but not before.

Just one thing: your patch removes the deletion of dead port within the
while (irqtab.tot_num_intr) loop. But then you have a horrible scenario:
you get an interrupt for the first and the second entry of the
queue, you start delivering the first, and in the meanwhile the user
process for the second entry dies. You'll be stuck within the while
(irqtab.tot_num_intr) loop.

I'm beginning to think that we should perhaps just drop that while
(irqtab.tot_num_intr) optimization, and just iterate over the whole
queue each time, using clear_wait() each time something is done, to make
sure we don't miss a wake.

Samuel