serial8250_interrupt idea

serial8250_interrupt idea

[George Spelvin]

When ISA-style edge-sensitive interrupts are shared (as is commonly done
on multi-serial cards), it's essential that all interrupt sources are
quieted before returning from the interrupt handler, so there will be
an inactive-to-active edge to trigger on next time.

This requires repeatedly polling all of the ports sharing one IRQ until
you've done a full pass during which nobody had an interrupt pending.
That ensures that there was an interval (between emptying the last
busy port and checking the status of the first empty port in the final
all-empty pass) during which the interrupt line was not asserted.

The current code keeps all the ports in a linked list and polls them
in a loop, remembering the position of the last busy port, until that
position has been reached again without seeing a non-empty port.

However, it seems to me that it's possible to improve on this.
Which would be valuable, given that ISA I/O port reads (usually on a
super-IO chip via an LPC bus these days) are quite time-consuming.

If you could predict which ports were going to be busy, you could check
them first on the first pass, allowing you to start the final verification
pass as early as possible.

This could be done very easily via a self-organizing list.  When a
port is polled busy, move it up to the front of the list so it will be
checked earlier next time.  The inactive ports would migrate to the end
of the list.  The struct uart_8250_port list is already locked for the
duration of the interrupt, so there is no need for additional locking.


I was thinking about preparing a patch to do this, but I have one style
question: it would be easier to do the list rearrangement if the
list were singly-linked.  Removing a port would require walking the
whole list, but we already do that each interrupt so it's hardly
a frightening cost.

Is there any reason to preserve the "struct list" configuration?

[PATCH 1/2] serial/8250.c: Change to singly linked handler chain.

[George Spelvin]

This is a prerequisite to the interesting patch 2/2.  This compiles,
but hasn't been tested yet.  It's out here for style comments.

This just converts the list of struct uart_8250_port attached to a single
IRQ from doubly linked to singly.  It should have no behavior differences.


---
 drivers/serial/8250.c |   93 +++++++++++++++++++++++++++----------------------
 1 files changed, 51 insertions(+), 42 deletions(-)

diff --git a/drivers/serial/8250.c b/drivers/serial/8250.c
index 18caa95..7f66335 100644
--- a/drivers/serial/8250.c
+++ b/drivers/serial/8250.c
@@ -116,7 +116,7 @@ static unsigned int probe_rsa_count;
 struct uart_8250_port {
 	struct uart_port	port;
 	struct timer_list	timer;		/* "no irq" timer */
-	struct list_head	list;		/* ports on this IRQ */
+	struct uart_8250_port	*next;		/* ports on this IRQ */
 	unsigned short		capabilities;	/* port capabilities */
 	unsigned short		bugs;		/* port bugs */
 	unsigned int		tx_loadsz;	/* transmit fifo load size */
@@ -146,7 +146,7 @@ struct uart_8250_port {
 
 struct irq_info {
 	spinlock_t		lock;
-	struct list_head	*head;
+	struct uart_8250_port	*head;
 };
 
 static struct irq_info irq_lists[NR_IRQS];
@@ -1432,13 +1432,16 @@ serial8250_handle_port(struct uart_8250_port *up)
 
 	spin_lock_irqsave(&up->port.lock, flags);
 
+	check_modem_status(up);
+
 	status = serial_inp(up, UART_LSR);
 
 	DEBUG_INTR("status = %x...", status);
 
-	if (status & (UART_LSR_DR | UART_LSR_BI))
+	if (status & (UART_LSR_DR | UART_LSR_BI)) {
 		receive_chars(up, &status);
-	check_modem_status(up);
+		check_modem_status(up);
+	}
 	if (status & UART_LSR_THRE)
 		transmit_chars(up);
 
@@ -1458,23 +1461,39 @@ serial8250_handle_port(struct uart_8250_port *up)
  *
  * This means we need to loop through all ports. checking that they
  * don't have an interrupt pending.
+ *
+ * Fencepost consideration: serial8250_handle_port only polls each
+ * interrupt source once; it does not itself loop until the port
+ * has deasserted the interrupt line.  Therefore, it is necessary to
+ * loop here until each port has had its IIR read in the idle state.
+ * "end" points to the beginning of the most recent run of idle ports.
+ * It is NULL if the current port is not idle.  The loop ends when we
+ * are about to check end again.
  */
 static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 {
 	struct irq_info *i = dev_id;
-	struct list_head *l, *end = NULL;
+	struct uart_8250_port *up, *end = NULL;
 	int pass_counter = 0, handled = 0;
 
 	DEBUG_INTR("serial8250_interrupt(%d)...", irq);
 
 	spin_lock(&i->lock);
 
-	l = i->head;
+	up = i->head;
 	do {
-		struct uart_8250_port *up;
 		unsigned int iir;
 
-		up = list_entry(l, struct uart_8250_port, list);
+		if (up == NULL) {
+			if (pass_counter++ > PASS_LIMIT) {
+				/* If we hit this, we're dead. */
+				printk(KERN_ERR "serial8250: too much work for "
+					"irq%d\n", irq);
+				break;
+			}
+			up = i->head;
+			continue;
+		}
 
 		iir = serial_in(up, UART_IIR);
 		if (!(iir & UART_IIR_NO_INT)) {
@@ -1486,9 +1505,10 @@ static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 		} else if (up->port.iotype == UPIO_DWAPB &&
 			  (iir & UART_IIR_BUSY) == UART_IIR_BUSY) {
 			/* The DesignWare APB UART has an Busy Detect (0x07)
-			 * interrupt meaning an LCR write attempt occured while the
-			 * UART was busy. The interrupt must be cleared by reading
-			 * the UART status register (USR) and the LCR re-written. */
+			 * interrupt meaning an LCR write attempt occured
+			 * while the UART was busy. The interrupt must
+			 * be cleared by reading the UART status register
+			 * (USR) and re-writing the LCR. */
 			unsigned int status;
 			status = *(volatile u32 *)up->port.private_data;
 			serial_out(up, UART_LCR, up->lcr);
@@ -1497,17 +1517,10 @@ static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 
 			end = NULL;
 		} else if (end == NULL)
-			end = l;
+			end = up;
 
-		l = l->next;
-
-		if (l == i->head && pass_counter++ > PASS_LIMIT) {
-			/* If we hit this, we're dead. */
-			printk(KERN_ERR "serial8250: too much work for "
-				"irq%d\n", irq);
-			break;
-		}
-	} while (l != end);
+		up = up->next;
+	} while (up != end);
 
 	spin_unlock(&i->lock);
 
@@ -1525,39 +1538,35 @@ static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
  */
 static void serial_do_unlink(struct irq_info *i, struct uart_8250_port *up)
 {
+	struct uart_8250_port *p, **pptr = &i->head;
+
 	spin_lock_irq(&i->lock);
 
-	if (!list_empty(i->head)) {
-		if (i->head == &up->list)
-			i->head = i->head->next;
-		list_del(&up->list);
-	} else {
-		BUG_ON(i->head != &up->list);
-		i->head = NULL;
+	while ((p = *pptr) != up) {
+		BUG_ON(p == NULL);
+		pptr = &p->next;
 	}
 
+	*pptr = up->next;
+
 	spin_unlock_irq(&i->lock);
 }
 
 static int serial_link_irq_chain(struct uart_8250_port *up)
 {
 	struct irq_info *i = irq_lists + up->port.irq;
-	int ret, irq_flags = up->port.flags & UPF_SHARE_IRQ ? IRQF_SHARED : 0;
+	int ret = 0;
+	struct uart_8250_port *head;
 
 	spin_lock_irq(&i->lock);
+	up->next = head = i->head;
+	i->head = up;
+	spin_unlock_irq(&i->lock);
 
-	if (i->head) {
-		list_add(&up->list, i->head);
-		spin_unlock_irq(&i->lock);
-
-		ret = 0;
-	} else {
-		INIT_LIST_HEAD(&up->list);
-		i->head = &up->list;
-		spin_unlock_irq(&i->lock);
-
+	if (!head) {
+		int irq_flag = up->port.flags & UPF_SHARE_IRQ ? IRQF_SHARED : 0;
 		ret = request_irq(up->port.irq, serial8250_interrupt,
-				  irq_flags, "serial", i);
+				  irq_flag, "serial", i);
 		if (ret < 0)
 			serial_do_unlink(i, up);
 	}
@@ -1570,8 +1579,8 @@ static void serial_unlink_irq_chain(struct uart_8250_port *up)
 	struct irq_info *i = irq_lists + up->port.irq;
 
 	BUG_ON(i->head == NULL);
-
-	if (list_empty(i->head))
+	serial_do_unlink(i, up);
+	if (i->head == NULL);
 		free_irq(up->port.irq, i);
 
 	serial_do_unlink(i, up);
-- 
1.5.6.5

[PATCH 2/2] serial/8250.c: Use self-adjusting list for port poll order.

[George Spelvin]

This is the interesting patch.  It changes the uart_8250_port list to
a self-adjusting one.  Busy ports move to the front, and idle ones
migrate to the end.  This reduces overal possing effort when there is
a mix of busy and idle ports.

Comments?

---
 drivers/serial/8250.c |   49 ++++++++++++++++++++++++++++++++++---------------
 1 files changed, 34 insertions(+), 15 deletions(-)

diff --git a/drivers/serial/8250.c b/drivers/serial/8250.c
index 7f66335..96e784f 100644
--- a/drivers/serial/8250.c
+++ b/drivers/serial/8250.c
@@ -1469,18 +1469,27 @@ serial8250_handle_port(struct uart_8250_port *up)
  * "end" points to the beginning of the most recent run of idle ports.
  * It is NULL if the current port is not idle.  The loop ends when we
  * are about to check end again.
+ *
+ * Optimization: this will finish sooner if we can check all busy
+ * ports first, starting the final verify-idle pass as soon as possible.
+ * To achieve this, busy ports are moved to the front of the list.
+ * *tailp marks the boundary between the front and the back of the list;
+ * when a port is found to be busy, it is removed from between *upp
+ * and upp->next, and reinserted at *tailp.
  */
 static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 {
 	struct irq_info *i = dev_id;
-	struct uart_8250_port *up, *end = NULL;
+	struct uart_8250_port *up, **upp, *end = NULL, **tailp;
 	int pass_counter = 0, handled = 0;
 
 	DEBUG_INTR("serial8250_interrupt(%d)...", irq);
 
+	tailp = upp = &i->head;
+
 	spin_lock(&i->lock);
 
-	up = i->head;
+	up = *upp;
 	do {
 		unsigned int iir;
 
@@ -1491,7 +1500,7 @@ static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 					"irq%d\n", irq);
 				break;
 			}
-			up = i->head;
+			tailp = upp = &i->head;
 			continue;
 		}
 
@@ -1499,11 +1508,8 @@ static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 		if (!(iir & UART_IIR_NO_INT)) {
 			serial8250_handle_port(up);
 
-			handled = 1;
-
-			end = NULL;
-		} else if (up->port.iotype == UPIO_DWAPB &&
-			  (iir & UART_IIR_BUSY) == UART_IIR_BUSY) {
+		} else if ((iir & UART_IIR_BUSY) == UART_IIR_BUSY &&
+			   up->port.iotype == UPIO_DWAPB) {
 			/* The DesignWare APB UART has an Busy Detect (0x07)
 			 * interrupt meaning an LCR write attempt occured
 			 * while the UART was busy. The interrupt must
@@ -1513,14 +1519,27 @@ static irqreturn_t serial8250_interrupt(int irq, void *dev_id)
 			status = *(volatile u32 *)up->port.private_data;
 			serial_out(up, UART_LCR, up->lcr);
 
-			handled = 1;
-
-			end = NULL;
-		} else if (end == NULL)
-			end = up;
+		} else {
+			/* Port does not have interrupt asserted. */
+			if (end == NULL)
+				end = up;	/* Start of run of idle ports */
+			upp = &up->next;	/* Do not move anything */
+			continue;
+		}
 
-		up = up->next;
-	} while (up != end);
+		/* up had activity */
+		handled = 1;
+		end = NULL;
+		/* Move to front of list; append after *tailp */
+		if (tailp != upp) {
+			*upp = up->next;
+			up->next = *tailp;
+			*tailp = up;
+			tailp = &up->next;
+		} else {
+			tailp = upp = &up->next;
+		}
+	} while ((up = *upp) != end);
 
 	spin_unlock(&i->lock);
 
-- 
1.5.6.5

RE: serial8250_interrupt idea

[Tosoni]

Hello Mr Spelvin,

When I put this kind of improvement in my serial drivers I usually run into
the following problem:

If several ports are very busy receiving at the same time, one of them gets
served much more often than the others, and the others start loosing data.

Does your changes take this into account ?

Sorry, I didn't take the time to go through your code (I'm working on un
unrelated project right now).

Regards

> -----Original Message-----
> From: linux-serial-owner@vger.kernel.org
> [mailto:linux-serial-owner@vger.kernel.org]On Behalf Of George Spelvin
> Sent: Thursday, November 13, 2008 4:03 PM
> To: linux-serial@vger.kernel.org
> Cc: alan@lxorguk.ukuu.org.uk; linux@horizon.com
> Subject: serial8250_interrupt idea
>
>
> When ISA-style edge-sensitive interrupts are shared (as is
> commonly done
> on multi-serial cards), it's essential that all interrupt sources are
> quieted before returning from the interrupt handler, so there will be
> an inactive-to-active edge to trigger on next time.
>
> This requires repeatedly polling all of the ports sharing one
> IRQ until
> you've done a full pass during which nobody had an interrupt pending.
> That ensures that there was an interval (between emptying the last
> busy port and checking the status of the first empty port in the final
> all-empty pass) during which the interrupt line was not asserted.
>
> The current code keeps all the ports in a linked list and polls them
> in a loop, remembering the position of the last busy port, until that
> position has been reached again without seeing a non-empty port.
>
> However, it seems to me that it's possible to improve on this.
> Which would be valuable, given that ISA I/O port reads (usually on a
> super-IO chip via an LPC bus these days) are quite time-consuming.
>
> If you could predict which ports were going to be busy, you
> could check
> them first on the first pass, allowing you to start the final
> verification
> pass as early as possible.
>
> This could be done very easily via a self-organizing list.  When a
> port is polled busy, move it up to the front of the list so it will be
> checked earlier next time.  The inactive ports would migrate
> to the end
> of the list.  The struct uart_8250_port list is already locked for the
> duration of the interrupt, so there is no need for additional locking.
>
>
> I was thinking about preparing a patch to do this, but I have
> one style
> question: it would be easier to do the list rearrangement if the
> list were singly-linked.  Removing a port would require walking the
> whole list, but we already do that each interrupt so it's hardly
> a frightening cost.
>
> Is there any reason to preserve the "struct list" configuration?
> --
> To unsubscribe from this list: send the line "unsubscribe
> linux-serial" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: serial8250_interrupt idea

[George Spelvin]

"Tosoni" <jp.tosoni@acksys.fr> wrote:
> When I put this kind of improvement in my serial drivers I usually run into
> the following problem:
>
> If several ports are very busy receiving at the same time, one of them gets
> served much more often than the others, and the others start losing data.
>
> Do your changes take this into account ?
>
> Sorry, I didn't take the time to go through your code (I'm working on un
> unrelated project right now).

I don't quite understand.

First of all, the patch only affects serial ports sharing the same
interrupt.  Are you talking about serial ports sharing the same interrupt,
or serial ports with different interrupts?

If you're talking about the latter, this patch will have no effect; it only
affects the way that multiple ports share the same interrupt.

And I don't understand how a problem like you describe can happen when
an interrupt is shared.  In that case, the hardware requires that all of
them are checked on every interrupt, and the driver has always done that.

Further, ports that have data waiting the first time they are checked
have to be re-checked until they are empty.  All the patch does is try
to reduce the number of times that idle ports are re-checked.

If there's a problem, though, perhaps I can figure it out while I'm
looking at this part of the code.  Can you describe it in greater detail?

RE: serial8250_interrupt idea

[Tosoni]

I am talking about serial ports sharing the same interrupt.
Here are more details.

Let's say that you have N ports sharing the same interrupt. When the data
rate is very high, or the processor is slow, the following may happen
depending on how you prioritize the ports:

say that high-speed frames of 150 chars arrive on ports X and Y.

1/ enter ISR
2/ test port X => process reception of a char, put it ahead of list
3/ during processing of 2/ another char arrived on X ; goto 2
4/ during processing of loop 2/ and 3/ many chars arrived on port Y, some
were lost
4/ process Y and other ports
5/ All N ports are now quiet; exit ISR

Now you have lost data on port Y because you prioritized X over Y.

Got it ?




> -----Original Message-----
> From: linux-serial-owner@vger.kernel.org
> [mailto:linux-serial-owner@vger.kernel.org]On Behalf Of George Spelvin
> Sent: Monday, November 17, 2008 11:56 AM
> To: jp.tosoni@acksys.fr
> Cc: linux@horizon.com; linux-serial@vger.kernel.org
> Subject: Re: serial8250_interrupt idea
>
>
> "Tosoni" <jp.tosoni@acksys.fr> wrote:
> > When I put this kind of improvement in my serial drivers I
> usually run into
> > the following problem:
> >
> > If several ports are very busy receiving at the same time,
> one of them gets
> > served much more often than the others, and the others
> start losing data.
> >
> > Do your changes take this into account ?
> >
> > Sorry, I didn't take the time to go through your code (I'm
> working on un
> > unrelated project right now).
>
> I don't quite understand.
>
> First of all, the patch only affects serial ports sharing the same
> interrupt.  Are you talking about serial ports sharing the
> same interrupt,
> or serial ports with different interrupts?
>
> If you're talking about the latter, this patch will have no
> effect; it only
> affects the way that multiple ports share the same interrupt.
>
> And I don't understand how a problem like you describe can happen when
> an interrupt is shared.  In that case, the hardware requires
> that all of
> them are checked on every interrupt, and the driver has
> always done that.
>
> Further, ports that have data waiting the first time they are checked
> have to be re-checked until they are empty.  All the patch does is try
> to reduce the number of times that idle ports are re-checked.
>
> If there's a problem, though, perhaps I can figure it out while I'm
> looking at this part of the code.  Can you describe it in
> greater detail?
> --
> To unsubscribe from this list: send the line "unsubscribe
> linux-serial" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: serial8250_interrupt idea

[George Spelvin]

"Tosoni" <jp.tosoni@acksys.fr> wrote:

> I am talking about serial ports sharing the same interrupt.
> Here are more details.
>
> Let's say that you have N ports sharing the same interrupt. When the data
> rate is very high, or the processor is slow, the following may happen
> depending on how you prioritize the ports:
>
> say that high-speed frames of 150 chars arrive on ports X and Y.
>
> 1/ enter ISR
> 2/ test port X => process reception of a char, put it ahead of list
> 3/ during processing of 2/ another char arrived on X ; goto 2
> 4/ during processing of loop 2/ and 3/ many chars arrived on port Y, some
> were lost
> 4/ process Y and other ports
> 5/ All N ports are now quiet; exit ISR
>
> Now you have lost data on port Y because you prioritized X over Y.
>
> Got it ?

I see how some port has to be checked first, so if others share the
same interrupt, they have to be checked second.  I don't see how this
means that "one of them gets served much more often than the others";
both get served equally often.

I also don't understand how the above can be a serious problem.
Although slow relative to CPU speeds, the I/O port accesses are extremely
fast relative to serial data transmission rates.  Even at 115,200 baud,
characters arrive every 86.8 us.  Once the interrupt handler is executing,
bytes are removed from the serial FIFO at around 1 per us.  So not even
a full character can arrive at port Y in the time it takes to completely
empty 64 bytes out of port X's FIFO.

In other words, your step 4/ cannot actually happen.  If one more
character is enough to cause port Y to overflow, it's perilously close
to overflowing without port X.

RE: serial8250_interrupt idea

[Chris Doré]

> George Spelvin wrote:
> In other words, your step 4/ cannot actually happen.

What if you consider interrupts of higher priority occurring?  That could
cause delays in your servicing of X.  I've encountered this before with high
speed ports on multiple interrupts, where one port continually steals time
from another.

..Chris

RE: serial8250_interrupt idea

[Tosoni]

Hi again,

I read your code more carefully and I believe that it does not
exhibit the problem I talked about. Sorry for argueing.

Please note however that these chips can be - and have been indeed -
used at much higher baudrates than the 115200 you mention. Once, I
have been using 1.8 Mbps on 2 ports, over RS422 links.

> I don't see how this means that "one of them gets served much
> more often than the others"; both get served equally often.
 
My wording was wrong, sorry. I rather meant "one of them gets served
before the others can get a chance to be served" so the first one, if
it is continually receiving, many delay service to the next ones, thus
loosing data.

Regards

> -----Original Message-----
> From: linux-serial-owner@vger.kernel.org
> [mailto:linux-serial-owner@vger.kernel.org]On Behalf Of George Spelvin
> Sent: Monday, November 17, 2008 2:45 PM
> To: jp.tosoni@acksys.fr
> Cc: linux@horizon.com; linux-serial@vger.kernel.org
> Subject: Re: serial8250_interrupt idea
> 
> 
> "Tosoni" <jp.tosoni@acksys.fr> wrote:
> 
> > I am talking about serial ports sharing the same interrupt.
> > Here are more details.
> >
> > Let's say that you have N ports sharing the same interrupt. 
> When the data
> > rate is very high, or the processor is slow, the following 
> may happen
> > depending on how you prioritize the ports:
> >
> > say that high-speed frames of 150 chars arrive on ports X and Y.
> >
> > 1/ enter ISR
> > 2/ test port X => process reception of a char, put it ahead of list
> > 3/ during processing of 2/ another char arrived on X ; goto 2
> > 4/ during processing of loop 2/ and 3/ many chars arrived 
> on port Y, some
> > were lost
> > 4/ process Y and other ports
> > 5/ All N ports are now quiet; exit ISR
> >
> > Now you have lost data on port Y because you prioritized X over Y.
> >
> > Got it ?
> 
> I see how some port has to be checked first, so if others share the
> same interrupt, they have to be checked second.  I don't see how this
> means that "one of them gets served much more often than the others";
> both get served equally often.
> 
> I also don't understand how the above can be a serious problem.
> Although slow relative to CPU speeds, the I/O port accesses 
> are extremely
> fast relative to serial data transmission rates.  Even at 
> 115,200 baud,
> characters arrive every 86.8 us.  Once the interrupt handler 
> is executing,
> bytes are removed from the serial FIFO at around 1 per us.  
> So not even
> a full character can arrive at port Y in the time it takes to 
> completely
> empty 64 bytes out of port X's FIFO.
> 
> In other words, your step 4/ cannot actually happen.  If one more
> character is enough to cause port Y to overflow, it's perilously close
> to overflowing without port X.
> --
> To unsubscribe from this list: send the line "unsubscribe 
> linux-serial" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>