Re: CSCAN I/O scheduler for 2.6.10 kernel

["Vishal Patil" <vishpat@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2723 bytes --]

I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.

- Vishal

On 4/5/06, Vishal Patil <vishpat@gmail.com> wrote:
> The two queues are used for sorting purposes ONLY. There is the
> dispatch queue to which the requests are moved from one of the queues
> and the request is processes of the dispatch queue.
>
> Example:
>
> Current request  = 40
> Q1 = 55 58 67 72
> Q2 = 10 23 38
>
> Assuming no other request arrives, these will be pushed on the
> dispatch queue in the following order
> 55 58 67 72 10 23 38
>
> I hope this clears things up.
>
> Also I have found that the patch that I had submitted earlier has few
> bugs in it. I am going to fix those and then submit a patch for 2.6.16
> Thanks.
>
>
> - Vishal
>
>
>
> On 4/5/06, Antonio Vargas <windenntw@gmail.com> wrote:
> > On 4/4/06, Vishal Patil <vishpat@gmail.com> wrote:
> > > In that case it would be a normal elevator algorithm and that has a
> > > possiblity of starving the requests at one end of the disk.
> > >
> > > - Vishal
> > >
> > > On 4/4/06, Bill Davidsen <davidsen@tmr.com> wrote:
> > > > Vishal Patil wrote:
> > > > > Maintain two queues which will be sorted in ascending order using Red
> > > > > Black Trees. When a disk request arrives and if the block number it
> > > > > refers to is greater than the block number of the current request
> > > > > being served add (merge) it to the first sorted queue or else add
> > > > > (merge) it to the second sorted queue. Keep on servicing the requests
> > > > > from the first request queue until it is empty after which switch over
> > > > > to the second queue and now reverse the roles of the two queues.
> > > > > Simple and Sweet. Many thanks for the awesome block I/O layer in the
> > > > > 2.6 kernel.
> > > > >
> > > > Why both queues sorting in ascending order? I would think that one
> > > > should be in descending order, which would reduce the seek distance
> > > > between the last i/o on one queue and the first on the next.
> > > >
> >
> > But, if there are two queues, one which is being processed and other
> > which gets the new requests (and the corresponding queue switch when
> > the current is empty), then there is no way to get starved when they
> > are sorted in opposite order.
> >
> >
> > --
> > Greetz, Antonio Vargas aka winden of network
> >
> > http://wind.codepixel.com/
> > windNOenSPAMntw@gmail.com
> > thesameasabove@amigascne.org
> >
> > Every day, every year
> > you have to work
> > you have to study
> > you have to scene.
> >
>
>
> --
> Every passing minute is another chance to turn it all around.
>


--
Every passing minute is another chance to turn it all around.

[-- Attachment #2: cscan-2.6.16.2-patch --]
[-- Type: application/octet-stream, Size: 11599 bytes --]

diff -urN linux-2.6.16.2/block/cscan.c linux-2.6.16.2-cscan/block/cscan.c
--- linux-2.6.16.2/block/cscan.c	1969-12-31 19:00:00.000000000 -0500
+++ linux-2.6.16.2-cscan/block/cscan.c	2006-04-09 10:24:52.000000000 -0400
@@ -0,0 +1,338 @@
+/*
+ * elevator cscan
+ */
+#include <linux/blkdev.h>
+#include <linux/elevator.h>
+#include <linux/bio.h>
+#include <linux/module.h>
+#include <linux/init.h>
+
+#define RQ_DATA(rq) ((struct cscan_request *) (rq)->elevator_private)
+
+#define RB_NONE         (2)
+#define RB_EMPTY(root)  ((root)->rb_node == NULL)
+#define ON_RB(node)     ((node)->rb_color != RB_NONE)
+#define RB_CLEAR(node)  ((node)->rb_color = RB_NONE)
+#define rb_entry_crq(node)      rb_entry((node), struct cscan_request, rb_node)
+#define DRQ_RB_ROOT(cd, crq)    (&(cd)->sort_list[rq_data_dir((crq)->request)])
+#define rq_rb_key(rq)           (rq)->sector
+
+
+struct cscan_data {
+        struct rb_root sort_list[2];
+        unsigned int count[2];
+        
+        sector_t last_sector;
+        unsigned int first;
+        mempool_t * crq_pool;
+};
+
+struct cscan_request {
+        struct rb_node rb_node;
+        sector_t rb_key;
+        unsigned int queue_id;
+
+        struct request * request;
+};
+
+static kmem_cache_t *crq_pool;
+
+/*
+ *      Searching/Sorting routines
+ */
+static struct cscan_request *
+__rb_insert_request(struct rb_root * root, struct cscan_request * crq) 
+{
+        struct rb_node **p = &root->rb_node;
+        struct rb_node *parent = NULL;
+        struct cscan_request * __crq;
+        
+         while(*p) {
+                parent = *p;
+                __crq = rb_entry(parent,struct cscan_request,rb_node);
+
+                if(crq->rb_key < __crq->rb_key) {
+                        p = &(*p)->rb_left;
+                } else if(crq->rb_key > __crq->rb_key) {
+                        p = &(*p)->rb_right;
+                } else {
+                        return __crq;
+                }
+        }
+        rb_link_node(&crq->rb_node,parent,p);
+        return NULL;
+} 
+
+static inline struct
+cscan_request * rb_insert_request(struct rb_root * root, 
+                                     struct cscan_request * crq)
+{
+        struct cscan_request * ret;
+        if((ret = __rb_insert_request(root,crq)))
+                goto out;
+        rb_insert_color(&crq->rb_node,root);
+out:
+        return ret;
+}
+
+static inline struct
+cscan_request * rb_find_request(struct rb_root * root, long key) 
+{
+        struct rb_node * n = root->rb_node;
+        struct cscan_request * crq;
+
+        while(n) 
+        {
+                crq = rb_entry(n,struct cscan_request,rb_node);
+
+                if (key > crq->rb_key) {
+                        n = n->rb_right;
+                } else if (key < crq->rb_key) {
+                        n = n->rb_left;
+                } else {
+                        return crq;
+                }
+        }
+        return NULL;
+}
+static void 
+cscan_remove_request(struct cscan_data * cd, struct cscan_request * crq) 
+{
+        rb_erase(&crq->rb_node, &cd->sort_list[crq->queue_id]);
+        RB_CLEAR(&crq->rb_node);
+        cd->count[crq->queue_id]--;
+}
+
+static void
+cscan_add_crq_rb(struct cscan_data * cd, struct cscan_request * crq) 
+{
+        crq->rb_key = rq_rb_key(crq->request);
+        rb_insert_request(&cd->sort_list[crq->queue_id],crq);
+        cd->count[crq->queue_id]++;
+}
+
+static void 
+cscan_merged_requests(request_queue_t *q, struct request *rq,
+				 struct request *next)
+{
+	struct cscan_data *cd = q->elevator->elevator_data;
+        struct cscan_request * crq;        
+        crq = RQ_DATA(rq);
+
+        cscan_remove_request(cd,crq);
+}
+
+static int 
+cscan_dispatch(request_queue_t *q, int force)
+{
+	struct cscan_data *cd = q->elevator->elevator_data;
+        struct rb_root * root = NULL;
+
+        if(rb_first(&cd->sort_list[cd->first])) {
+               root = &cd->sort_list[cd->first]; 
+        } else if(rb_first(&cd->sort_list[1 - cd->first])) {
+                root = &cd->sort_list[1 - cd->first]; 
+                cd->first = 1 - cd->first; 
+        }
+
+	if (root) {
+		struct cscan_request *crq;
+                struct request * rq;
+                
+		crq = rb_entry_crq(rb_first(root));
+                rq = crq->request;
+                cscan_remove_request(cd,crq);
+                cd->last_sector = rq->sector + rq->nr_sectors;
+		elv_dispatch_sort(q, rq);
+		return 1;
+	}
+	return 0;
+}
+
+static void 
+cscan_add_request(request_queue_t *q, struct request *rq)
+{
+	struct cscan_data *cd = q->elevator->elevator_data;
+        struct cscan_request * crq;        
+        
+        crq = RQ_DATA(rq);
+        if(rq->sector > cd->last_sector) 
+                crq->queue_id = cd->first;
+        else 
+                crq->queue_id = 1 - cd->first;
+        cscan_add_crq_rb(cd,crq);                                 
+}
+
+static int 
+cscan_queue_empty(request_queue_t *q)
+{
+	struct cscan_data *cd = q->elevator->elevator_data;
+
+        return ((rb_first(&cd->sort_list[cd->first]) == NULL) && 
+                (rb_first(&cd->sort_list[1 - cd->first]) == NULL));
+}
+
+static struct request *
+cscan_former_request(request_queue_t *q, struct request *rq)
+{
+	struct cscan_data *cd = q->elevator->elevator_data;
+        struct cscan_request * crq = RQ_DATA(rq); 
+       
+        if((crq->queue_id == cd->first) && (rb_prev(&crq->rb_node) == NULL))
+                return NULL;
+        
+        if( (crq->queue_id == (1 - cd->first)) && 
+                                (rb_prev(&crq->rb_node) == NULL)){
+                if(rb_last(&cd->sort_list[cd->first])){
+                	crq = rb_entry_crq(rb_last(
+                                &cd->sort_list[cd->first]));
+                        return crq->request;                                
+                } else {
+                        return NULL;
+                }
+        }            
+        
+        return rb_entry_crq(rb_prev(&crq->rb_node))->request;
+}
+
+static struct request *
+cscan_latter_request(request_queue_t *q, struct request *rq)
+{
+	struct cscan_data *cd = q->elevator->elevator_data;
+        struct cscan_request * crq = RQ_DATA(rq); 
+       
+        if((crq->queue_id == (1 - cd->first)) && 
+                                (rb_next(&crq->rb_node) == NULL))
+                return NULL;
+        
+        if( (crq->queue_id == cd->first) && 
+                                (rb_next(&crq->rb_node) == NULL)){
+                if(rb_first(&cd->sort_list[1 - cd->first])){
+                	crq = rb_entry_crq(rb_first(
+                                &cd->sort_list[1 - cd->first]));
+                        return crq->request;                                
+                } else {
+                        return NULL;
+                }
+        }            
+        
+        return rb_entry_crq(rb_next(&crq->rb_node))->request;
+
+}
+
+static void 
+cscan_put_request(request_queue_t *q, struct request * rq) 
+{
+        struct cscan_data * cd = q->elevator->elevator_data;
+        struct cscan_request *crq = RQ_DATA(rq);
+
+        mempool_free(crq,cd->crq_pool);
+        rq->elevator_private = NULL;
+}
+
+static int
+cscan_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
+                     gfp_t gfp_mask)
+{
+        struct cscan_data * cd = q->elevator->elevator_data;
+        struct cscan_request * crq;
+        
+        crq = mempool_alloc(cd->crq_pool,gfp_mask);
+        if(crq) {
+                memset(crq,0,sizeof(*crq));
+                RB_CLEAR(&crq->rb_node);
+                crq->request = rq;
+                rq->elevator_private = crq;
+                return 0;
+        }
+        return 1;
+}
+
+
+static int 
+cscan_init_queue(request_queue_t *q, elevator_t *e)
+{
+	struct cscan_data *cd;
+        int i = 0;
+
+	cd = kmalloc(sizeof(*cd), GFP_KERNEL);
+	if (!cd)
+		return -ENOMEM;
+                
+        cd->first = 0;
+        cd->last_sector = 0;
+        for(i=0;i<2;i++) {
+                cd->sort_list[i] = RB_ROOT;
+                cd->count[i]     = 0;
+        }
+	e->elevator_data = cd;
+
+        cd->crq_pool = mempool_create(BLKDEV_MIN_RQ,mempool_alloc_slab,
+                        mempool_free_slab,crq_pool);
+
+       if(!cd->crq_pool) {
+                kfree(cd);
+                return -ENOMEM;
+       }
+	return 0;
+}
+
+static void 
+cscan_exit_queue(elevator_t *e)
+{
+	struct cscan_data *cd = e->elevator_data;
+
+        BUG_ON(rb_first(&cd->sort_list[cd->first]) != NULL);
+        BUG_ON(rb_first(&cd->sort_list[1 - cd->first]) != NULL);
+
+	kfree(cd);
+}
+
+static struct elevator_type elevator_cscan = {
+	.ops = {
+		.elevator_merge_req_fn		= cscan_merged_requests,
+		.elevator_dispatch_fn		= cscan_dispatch,
+		.elevator_add_req_fn		= cscan_add_request,
+		.elevator_queue_empty_fn	= cscan_queue_empty,
+		.elevator_former_req_fn		= cscan_former_request,
+		.elevator_latter_req_fn		= cscan_latter_request,
+                .elevator_set_req_fn            = cscan_set_request,
+                .elevator_put_req_fn            = cscan_put_request,
+		.elevator_init_fn		= cscan_init_queue,
+		.elevator_exit_fn		= cscan_exit_queue,
+	},
+	.elevator_name = "cscan",
+	.elevator_owner = THIS_MODULE,
+};
+
+static int __init 
+cscan_init(void)
+{
+        int ret;
+
+        crq_pool = kmem_cache_create("cscan_crq", sizeof(struct cscan_request),
+                                     0, 0, NULL, NULL);
+        if (!crq_pool)
+                 return -ENOMEM;
+
+        ret = elv_register(&elevator_cscan);
+        if(ret)
+                kmem_cache_destroy(crq_pool);
+        
+        return ret;
+}
+
+static void __exit 
+cscan_exit(void)
+{
+        kmem_cache_destroy(crq_pool);
+	elv_unregister(&elevator_cscan);
+}
+
+module_init(cscan_init);
+module_exit(cscan_exit);
+
+
+MODULE_AUTHOR("Vishal Patil");
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("CSCAN I/O scheduler");
diff -urN linux-2.6.16.2/block/Kconfig.iosched linux-2.6.16.2-cscan/block/Kconfig.iosched
--- linux-2.6.16.2/block/Kconfig.iosched	2006-04-07 12:56:47.000000000 -0400
+++ linux-2.6.16.2-cscan/block/Kconfig.iosched	2006-04-09 10:25:07.000000000 -0400
@@ -11,6 +11,19 @@
 	  that do their own scheduling and require only minimal assistance from
 	  the kernel.
 
+config IOSCHED_CSCAN
+	bool
+	default y
+	---help---
+        CSCAN I/O scheduler. Maintain two queues which will be sorted in
+        ascending order using Red Black Trees. When a disk request arrives and
+        if the block number it refers to is greater than the block number of the
+        current request being served add (merge) it to the first sorted queue or
+        else add (merge) it to the second sorted queue. Keep on servicing the
+        requests from the first request queue until it is empty after which
+        switch over to the second queue and now reverse the roles of the two
+        queues
+
 config IOSCHED_AS
 	tristate "Anticipatory I/O scheduler"
 	default y
diff -urN linux-2.6.16.2/block/Makefile linux-2.6.16.2-cscan/block/Makefile
--- linux-2.6.16.2/block/Makefile	2006-04-07 12:56:47.000000000 -0400
+++ linux-2.6.16.2-cscan/block/Makefile	2006-04-09 10:24:58.000000000 -0400
@@ -5,6 +5,7 @@
 obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o
 
 obj-$(CONFIG_IOSCHED_NOOP)	+= noop-iosched.o
+obj-$(CONFIG_IOSCHED_CSCAN)	+= cscan.o
 obj-$(CONFIG_IOSCHED_AS)	+= as-iosched.o
 obj-$(CONFIG_IOSCHED_DEADLINE)	+= deadline-iosched.o
 obj-$(CONFIG_IOSCHED_CFQ)	+= cfq-iosched.o