Re: [PATCH 5/6] sctp multistream scheduling: a sample priority queue scheduling module
From: Yaogong Wang
Date: Sat Jun 05 2010 - 16:03:15 EST
On Thu, Jun 3, 2010 at 9:06 AM, Vlad Yasevich <vladislav.yasevich@xxxxxx> wrote:
>
>
> Yaogong Wang wrote:
>> A sample priority queue scheduling module that uses our interface
>>
>> Signed-off-by: Yaogong Wang <ywang15@xxxxxxxx>
>> ---
>> diff -uprN -X linux-2.6.32.8/Documentation/dontdiff
>> p4/net/sctp/Kconfig p5/net/sctp/Kconfig
>> --- p4/net/sctp/Kconfig 2010-05-28 11:48:55.000000000 -0700
>> +++ p5/net/sctp/Kconfig 2010-05-28 14:43:17.000000000 -0700
>> @@ -37,6 +37,12 @@ menuconfig IP_SCTP
>>
>> if IP_SCTP
>>
>> +config SCTP_SCHED_PRIO
>> + tristate "SCTP Multistream Scheduling: Priority Queue"
>> + default m
>> + help
>> + Use priority queue to schedule among multiple streams
>> +
>> config SCTP_DBG_MSG
>> bool "SCTP: Debug messages"
>> help
>> diff -uprN -X linux-2.6.32.8/Documentation/dontdiff
>> p4/net/sctp/Makefile p5/net/sctp/Makefile
>> --- p4/net/sctp/Makefile 2010-05-28 11:48:55.000000000 -0700
>> +++ p5/net/sctp/Makefile 2010-05-28 14:48:08.000000000 -0700
>> @@ -11,6 +11,7 @@ sctp-y := sm_statetable.o sm_statefuns.o
>> tsnmap.o bind_addr.o socket.o primitive.o \
>> output.o input.o debug.o ssnmap.o auth.o sched.o
>>
>> +obj-$(CONFIG_SCTP_SCHED_PRIO) += sctp_prio.o
>> sctp-$(CONFIG_SCTP_DBG_OBJCNT) += objcnt.o
>> sctp-$(CONFIG_PROC_FS) += proc.o
>> sctp-$(CONFIG_SYSCTL) += sysctl.o
>> diff -uprN -X linux-2.6.32.8/Documentation/dontdiff
>> p4/net/sctp/sctp_prio.c p5/net/sctp/sctp_prio.c
>> --- p4/net/sctp/sctp_prio.c 1969-12-31 16:00:00.000000000 -0800
>> +++ p5/net/sctp/sctp_prio.c 2010-06-02 13:09:33.000000000 -0700
>> @@ -0,0 +1,108 @@
>> +/*
>> + * Priority queue scheduling among multiple SCTP streams
>> + */
>> +
>> +#include <linux/module.h>
>> +#include <linux/types.h>
>> +#include <linux/list.h>
>> +#include <net/sctp/sctp.h>
>> +
>> +static int zero_high_prio = 1;
>> +module_param(zero_high_prio, int, 0644);
>> +MODULE_PARM_DESC(zero_high_prio, "zero indicates highest priority?");
>> +
>> +static int prio_init(struct sctp_outq *q, gfp_t gfp)
>> +{
>> + __u16 i;
>> + q->out_chunk_list = kmalloc(q->asoc->c.sinit_num_ostreams
>> + * sizeof(struct list_head), gfp);
>
> This could end up wasting quite a lot of space since the queue is initialized
> prior to ostreams negotiation.
>
I agree. Refer to my discussion on the design issue of when to set the
socket option.
>
>> + if (!q->out_chunk_list)
>> + return -ENOMEM;
>> + for (i = 0; i < q->asoc->c.sinit_num_ostreams; i++)
>> + INIT_LIST_HEAD(&q->out_chunk_list[i]);
>> +
>> + return 0;
>> +}
>> +
>> +static void prio_release(struct sctp_outq *q)
>> +{
>> + kfree(q->out_chunk_list);
>> + return;
>> +}
>> +
>> +static void prio_enqueue_head_data(struct sctp_outq *q,
>> + struct sctp_chunk *ch)
>> +{
>> + list_add(&ch->list, &q->out_chunk_list[ch->sinfo.sinfo_stream]);
>> + q->out_qlen += ch->skb->len;
>> + return;
>> +}
>> +
>> +static void prio_enqueue_tail_data(struct sctp_outq *q, struct sctp_chunk *ch)
>> +{
>> + list_add_tail(&ch->list, &q->out_chunk_list[ch->sinfo.sinfo_stream]);
>> + q->out_qlen += ch->skb->len;
>> + return;
>> +}
>> +
>> +static struct sctp_chunk *prio_dequeue_data(struct sctp_outq *q)
>> +{
>> + struct sctp_chunk *ch = NULL;
>> + __u16 prio = 0, i, cur = 0;
>> + int flag = 0;
>> +
>> + for (i = 0; i < q->asoc->c.sinit_num_ostreams; i++) {
>> + if (!list_empty(&q->out_chunk_list[i]) && (flag == 0
>> + || (zero_high_prio ? q->asoc->sched_priv[i] < prio
>> + : q->asoc->sched_priv[i] > prio))) {
>
> Can you please simplify this conditional. Also, the logical operands
> typically end the line, not start it.
will do it
>
>> + cur = i;
>> + flag = 1;
>> + prio = q->asoc->sched_priv[i];
>> + }
>> + }
>> +
>
> It might be nice to cache the asoc so you don't have to keep dereferencing the
> queue.
>
If I move sched_ops from sctp_association to sctp_outq as per your
suggestion, the problem is automatically solved.
> Also, isn't there a strong starvation possibility if a higher priority queue
> gets most of data?
>
Yes, starvation is possible in this algorithm. However, the philosophy
is that, as the user chooses the scheduling algorithm, he should be
aware of this. If he doesn't want this, he may use other scheduling
algorithms or implement his own. We provide mechanism. The user
decides his policy.
Yaogong
> -vlad
>
>> + if (flag) {
>> + struct list_head *entry = q->out_chunk_list[cur].next;
>> + ch = list_entry(entry, struct sctp_chunk, list);
>> + list_del_init(entry);
>> + q->out_qlen -= ch->skb->len;
>> + }
>> + return ch;
>> +}
>> +
>> +static inline int prio_is_empty(struct sctp_outq *q)
>> +{
>> + __u16 i;
>> + for (i = 0; i < q->asoc->c.sinit_num_ostreams; i++)
>> + if (!list_empty(&q->out_chunk_list[i]))
>> + return 0;
>> + return 1;
>> +}
>> +
>> +static struct sctp_sched_ops sctp_prio = {
>> + .name = "prio",
>> + .owner = THIS_MODULE,
>> + .init = prio_init,
>> + .release = prio_release,
>> + .enqueue_head_data = prio_enqueue_head_data,
>> + .enqueue_tail_data = prio_enqueue_tail_data,
>> + .dequeue_data = prio_dequeue_data,
>> + .is_empty = prio_is_empty,
>> +};
>> +
>> +static int __init sctp_prio_register(void)
>> +{
>> + return sctp_register_sched(&sctp_prio);
>> +}
>> +
>> +static void __exit sctp_prio_unregister(void)
>> +{
>> + sctp_unregister_sched(&sctp_prio);
>> +}
>> +
>> +module_init(sctp_prio_register);
>> +module_exit(sctp_prio_unregister);
>> +
>> +MODULE_AUTHOR("Yaogong Wang");
>> +MODULE_LICENSE("GPL");
>> +MODULE_DESCRIPTION("SCTP Multistream Scheduling: Priority Queue");
>>
>
>
--
========================
Yaogong Wang, PhD candidate
Department of Computer Science
North Carolina State University
http://www4.ncsu.edu/~ywang15/
========================
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/