[PATCH 2.4] : IrLMP basic socket scheduler (to make 2.4.21-pre2 compile)

Jean Tourrilhes (jt@bougret.hpl.hp.com)
Wed, 18 Dec 2002 18:40:45 -0800


Hi Marcelo,

One of the IrDA patch I sent you didn't made it into the
kernel. That's unfortunate because it was one half of a complete
patch, and as the other part is in the kernel, the IrDA stack is not
functional (see previous e-mail).
I've rediffed the patch against 2.4.21-pre2 to avoid the fuzz,
and it is included below. Would you mind including that in the kernel ?

Regards,

Jean

ir241_flow_sched_lap_lmp-7.diff :
-------------------------------
o [FEATURE] Reduce LAP Tx queue to 2 packets (from 10)
Improve latency, reduce buffer usage
o [FEATURE] LAP Tx queue not full notification (flow start)
Poll higher layer to fill synchronously LAP window (7 packets)
o [FEATURE] LMP LSAP scheduler
Ensure Tx fairness between LSAPs (sockets, IrCOMM, IrNET...)

<And I might add...>
o [CRITICA] Required by the IrTTP patch already in 2.4.21-pre2

diff -u -p -r linux/include/net/irda/irlap.d6.h linux/include/net/irda/irlap.h
--- linux/include/net/irda/irlap.d6.h Wed Dec 18 17:54:47 2002
+++ linux/include/net/irda/irlap.h Wed Dec 18 17:56:13 2002
@@ -50,8 +50,32 @@
#define CBROADCAST 0xfe /* Connection broadcast address */
#define XID_FORMAT 0x01 /* Discovery XID format */

+/* Nobody seems to use this constant. */
#define LAP_WINDOW_SIZE 8
-#define LAP_MAX_QUEUE 10
+/* We keep the LAP queue very small to minimise the amount of buffering.
+ * this improve latency and reduce resource consumption.
+ * This work only because we have synchronous refilling of IrLAP through
+ * the flow control mechanism (via scheduler and IrTTP).
+ * 2 buffers is the minimum we can work with, one that we send while polling
+ * IrTTP, and another to know that we should not send the pf bit.
+ * Jean II */
+#define LAP_HIGH_THRESHOLD 2
+/* Some rare non TTP clients don't implement flow control, and
+ * so don't comply with the above limit (and neither with this one).
+ * For IAP and management, it doesn't matter, because they never transmit much.
+ *.For IrLPT, this should be fixed.
+ * - Jean II */
+#define LAP_MAX_QUEUE 10
+/* Please note that all IrDA management frames (LMP/TTP conn req/disc and
+ * IAS queries) fall in the second category and are sent to LAP even if TTP
+ * is stopped. This means that those frames will wait only a maximum of
+ * two (2) data frames before beeing sent on the "wire", which speed up
+ * new socket setup when the link is saturated.
+ * Same story for two sockets competing for the medium : if one saturates
+ * the LAP, when the other want to transmit it only has to wait for
+ * maximum three (3) packets (2 + one scheduling), which improve performance
+ * of delay sensitive applications.
+ * Jean II */

#define NR_EXPECTED 1
#define NR_UNEXPECTED 0
diff -u -p -r linux/include/net/irda/irlmp.d6.h linux/include/net/irda/irlmp.h
--- linux/include/net/irda/irlmp.d6.h Wed Dec 18 17:54:56 2002
+++ linux/include/net/irda/irlmp.h Wed Dec 18 17:56:13 2002
@@ -132,6 +132,7 @@ struct lap_cb {

struct irlap_cb *irlap; /* Instance of IrLAP layer */
hashbin_t *lsaps; /* LSAP associated with this link */
+ struct lsap_cb *flow_next; /* Next lsap to be polled for Tx */

__u8 caddr; /* Connection address */
__u32 saddr; /* Source device address */
@@ -235,6 +236,7 @@ void irlmp_connless_data_indication(stru

void irlmp_status_request(void);
void irlmp_status_indication(struct lap_cb *, LINK_STATUS link, LOCK_STATUS lock);
+void irlmp_flow_indication(struct lap_cb *self, LOCAL_FLOW flow);

int irlmp_slsap_inuse(__u8 slsap);
__u8 irlmp_find_free_slsap(void);
@@ -252,7 +254,9 @@ extern struct irlmp_cb *irlmp;

static inline hashbin_t *irlmp_get_cachelog(void) { return irlmp->cachelog; }

-static inline int irlmp_get_lap_tx_queue_len(struct lsap_cb *self)
+/* Check if LAP queue is full.
+ * Used by IrTTP for low control, see comments in irlap.h - Jean II */
+static inline int irlmp_lap_tx_queue_full(struct lsap_cb *self)
{
if (self == NULL)
return 0;
@@ -261,7 +265,7 @@ static inline int irlmp_get_lap_tx_queue
if (self->lap->irlap == NULL)
return 0;

- return IRLAP_GET_TX_QUEUE_LEN(self->lap->irlap);
+ return(IRLAP_GET_TX_QUEUE_LEN(self->lap->irlap) >= LAP_HIGH_THRESHOLD);
}

/* After doing a irlmp_dup(), this get one of the two socket back into
diff -u -p -r linux/net/irda/irlap_event.d6.c linux/net/irda/irlap_event.c
--- linux/net/irda/irlap_event.d6.c Wed Dec 18 17:55:32 2002
+++ linux/net/irda/irlap_event.c Wed Dec 18 17:56:13 2002
@@ -253,19 +253,45 @@ void irlap_do_event(struct irlap_cb *sel
case LAP_XMIT_P: /* FALLTHROUGH */
case LAP_XMIT_S:
/*
+ * We just received the pf bit and are at the beginning
+ * of a new LAP transmit window.
* Check if there are any queued data frames, and do not
* try to disconnect link if we send any data frames, since
* that will change the state away form XMIT
*/
+ IRDA_DEBUG(2, __FUNCTION__ "() : queue len = %d\n",
+ skb_queue_len(&self->txq));
+
if (skb_queue_len(&self->txq)) {
/* Prevent race conditions with irlap_data_request() */
self->local_busy = TRUE;

+ /* Theory of operation.
+ * We send frames up to when we fill the window or
+ * reach line capacity. Those frames will queue up
+ * in the device queue, and the driver will slowly
+ * send them.
+ * After each frame that we send, we poll the higher
+ * layer for more data. It's the right time to do
+ * that because the link layer need to perform the mtt
+ * and then send the first frame, so we can afford
+ * to send a bit of time in kernel space.
+ * The explicit flow indication allow to minimise
+ * buffers (== lower latency), to avoid higher layer
+ * polling via timers (== less context switches) and
+ * to implement a crude scheduler - Jean II */
+
/* Try to send away all queued data frames */
while ((skb = skb_dequeue(&self->txq)) != NULL) {
+ /* Send one frame */
ret = (*state[self->state])(self, SEND_I_CMD,
skb, NULL);
kfree_skb(skb);
+
+ /* Poll the higher layers for one more frame */
+ irlmp_flow_indication(self->notify.instance,
+ FLOW_START);
+
if (ret == -EPROTO)
break; /* Try again later! */
}
diff -u -p -r linux/net/irda/irlmp.d6.c linux/net/irda/irlmp.c
--- linux/net/irda/irlmp.d6.c Wed Dec 18 17:55:46 2002
+++ linux/net/irda/irlmp.c Wed Dec 18 17:56:13 2002
@@ -1220,6 +1220,72 @@ void irlmp_status_indication(struct lap_
}

/*
+ * Receive flow control indication from LAP.
+ * LAP want us to send it one more frame. We implement a simple round
+ * robin scheduler between the active sockets so that we get a bit of
+ * fairness. Note that the round robin is far from perfect, but it's
+ * better than nothing.
+ * We then poll the selected socket so that we can do synchronous
+ * refilling of IrLAP (which allow to minimise the number of buffers).
+ * Jean II
+ */
+void irlmp_flow_indication(struct lap_cb *self, LOCAL_FLOW flow)
+{
+ struct lsap_cb *next;
+ struct lsap_cb *curr;
+ int lsap_todo;
+
+ ASSERT(self->magic == LMP_LAP_MAGIC, return;);
+ ASSERT(flow == FLOW_START, return;);
+
+ /* Get the number of lsap. That's the only safe way to know
+ * that we have looped around... - Jean II */
+ lsap_todo = HASHBIN_GET_SIZE(self->lsaps);
+ IRDA_DEBUG(4, __FUNCTION__ "() : %d lsaps to scan\n", lsap_todo);
+
+ /* Poll lsap in order until the queue is full or until we
+ * tried them all.
+ * Most often, the current LSAP will have something to send,
+ * so we will go through this loop only once. - Jean II */
+ while((lsap_todo--) &&
+ (IRLAP_GET_TX_QUEUE_LEN(self->irlap) < LAP_HIGH_THRESHOLD)) {
+ /* Try to find the next lsap we should poll. */
+ next = self->flow_next;
+ if(next != NULL) {
+ /* Note that if there is only one LSAP on the LAP
+ * (most common case), self->flow_next is always NULL,
+ * so we always avoid this loop. - Jean II */
+ IRDA_DEBUG(4, __FUNCTION__ "() : searching my LSAP\n");
+
+ /* We look again in hashbins, because the lsap
+ * might have gone away... - Jean II */
+ curr = (struct lsap_cb *) hashbin_get_first(self->lsaps);
+ while((curr != NULL ) && (curr != next))
+ curr = (struct lsap_cb *) hashbin_get_next(self->lsaps);
+ } else
+ curr = NULL;
+
+ /* If we have no lsap, restart from first one */
+ if(curr == NULL)
+ curr = (struct lsap_cb *) hashbin_get_first(self->lsaps);
+ /* Uh-oh... Paranoia */
+ if(curr == NULL)
+ break;
+
+ /* Next time, we will get the next one (or the first one) */
+ self->flow_next = (struct lsap_cb *) hashbin_get_next(self->lsaps);
+ IRDA_DEBUG(4, __FUNCTION__ "() : curr is %p, next was %p and is now %p, still %d to go - queue len = %d\n", curr, next, self->flow_next, lsap_todo, IRLAP_GET_TX_QUEUE_LEN(self->irlap));
+
+ /* Inform lsap user that it can send one more packet. */
+ if (curr->notify.flow_indication != NULL)
+ curr->notify.flow_indication(curr->notify.instance,
+ curr, flow);
+ else
+ IRDA_DEBUG(1, __FUNCTION__ "(), no handler\n");
+ }
+}
+
+/*
* Function irlmp_hint_to_service (hint)
*
* Returns a list of all servics contained in the given hint bits. This
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/