CSCAN I/O scheduler for 2.6.10 kernel

CSCAN I/O scheduler for 2.6.10 kernel

[Vishal Patil]

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

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.

- Vishal

PS: Please note that I have not subscribed to the LKML. For comments
please reply back to this email.

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

[-- Attachment #2: linux-2.6.10-cscan.patch --]
[-- Type: application/octet-stream, Size: 17138 bytes --]

diff -urN linux-2.6.10/drivers/block/cscan.c linux-2.6.10-cscan/drivers/block/cscan.c
--- linux-2.6.10/drivers/block/cscan.c	1969-12-31 19:00:00.000000000 -0500
+++ linux-2.6.10-cscan/drivers/block/cscan.c	2006-03-30 21:34:27.000000000 -0500
@@ -0,0 +1,512 @@
+/*
+ * CSCAN scheduler for 2.6 kernel 
+ */
+#include <linux/kernel.h>
+#include <linux/fs.h>
+#include <linux/blkdev.h>
+#include <linux/elevator.h>
+#include <linux/bio.h>
+#include <linux/config.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/init.h>
+#include <linux/compiler.h>
+#include <linux/rbtree.h>
+#include <linux/hash.h>
+#include <asm/uaccess.h>
+
+static const int cscan_hash_shift = 5;
+#define DL_HASH_BLOCK(sec)      ((sec) >> 3)
+#define DL_HASH_FN(sec)         \
+        (hash_long(DL_HASH_BLOCK((sec)),cscan_hash_shift))
+#define DL_HASH_ENTRIES         (1 << cscan_hash_shift)
+#define rq_hash_key(rq)         ((rq)->sector + (rq)->nr_sectors)
+#define list_entry_hash(ptr)    list_entry((ptr), struct CSCAN_request, hash)
+#define ON_HASH(crq)            (crq)->on_hash
+
+
+#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 rq_rb_key(rq)   (rq)->sector
+
+struct CSCAN_data {
+        unsigned int curr;
+        struct rb_root sort_list[2]; /* Used to keep a sorted list of requests*/
+        unsigned int count[2];
+        
+        struct list_head * dispatch;
+        struct list_head * hash;
+        
+        mempool_t * crq_pool;          /* Pool of requests*/
+
+        sector_t last_sector;
+};
+
+/*
+ *      Per-request data       
+ */
+struct CSCAN_request {
+        struct rb_node rb_node;
+        sector_t rb_key;
+        struct request * request;
+        
+        struct list_head hash;
+        char on_hash;
+        
+        unsigned char queue_id; /* Which queue is this request on */
+};
+
+
+/*
+ *      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 struct request *
+cscan_find_crq_rb(struct CSCAN_data * cd, sector_t sector) {
+        struct CSCAN_request * crq;
+        int i = 0;
+ 
+        for(i=0;i<2;i++) {
+                crq = rb_find_request(&cd->sort_list[i],sector);
+                if(crq)
+                        return crq->request;
+        }
+
+        return NULL;
+}
+
+static inline void
+cscan_del_crq_rb(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 inline void
+cscan_add_crq_rb(struct CSCAN_data *cd, struct CSCAN_request *crq)
+{
+        rb_insert_request(&cd->sort_list[crq->queue_id],crq);
+        cd->count[crq->queue_id]++;
+
+}
+static inline void
+cscan_del_crq_hash(struct CSCAN_request * crq) {
+        if(ON_HASH(crq)) {
+                crq->on_hash = 0;
+                list_del_init(&crq->hash);
+        }
+}
+
+static struct request * 
+cscan_find_rq_hash(struct CSCAN_data *cd, sector_t sector) {
+        struct list_head *hash_list = &cd->hash[DL_HASH_FN(sector)];
+        struct list_head *entry, *next = hash_list->next;
+
+        while ((entry = next) != hash_list) {
+                struct CSCAN_request *crq = list_entry_hash(entry);
+                struct request *__rq = crq->request;
+
+                next = entry->next;
+
+                BUG_ON(!ON_HASH(crq));
+
+                if (!rq_mergeable(__rq)) {
+                        cscan_del_crq_hash(crq);
+                        continue;
+                }
+
+                if (rq_hash_key(__rq) == sector)
+                        return __rq;
+        }
+
+        return NULL;
+
+
+}
+
+static kmem_cache_t * crq_pool;
+
+
+
+static inline void
+cscan_add_crq_hash(struct CSCAN_data * cd, struct CSCAN_request * crq) {
+        struct request *rq = crq->request;
+
+        BUG_ON(ON_HASH(crq));
+        crq->on_hash = 1;
+        list_add(&crq->hash, &cd->hash[DL_HASH_FN(rq_hash_key(rq))]);
+}
+
+static void
+cscan_remove_request(struct CSCAN_data *cd, struct CSCAN_request * crq,
+                                int queue) {
+        struct request * rq;
+        
+        cscan_del_crq_hash(crq);
+        rq = crq->request;
+        list_add_tail(&rq->queuelist, cd->dispatch);
+        cscan_del_crq_rb(cd,crq);
+}
+
+static int
+cscan_move_requests_to_dispatch_queue(struct CSCAN_data * cd,int queue) {
+        struct rb_node * node;
+        struct CSCAN_request * crq;
+        int ret = 0;
+        
+        node = rb_first(&cd->sort_list[queue]);
+                
+        while(node) {
+                crq  = rb_entry(node,struct CSCAN_request,rb_node);
+                node = rb_next(node);
+                cscan_remove_request(cd,crq,queue); 
+                ret = 1;
+        }
+
+        return ret;
+}
+
+static int 
+cscan_dispatch_requests(struct CSCAN_data * cd) {
+        int ret1,ret2;
+        
+        ret1 = cscan_move_requests_to_dispatch_queue(cd,cd->curr);
+        ret2 = cscan_move_requests_to_dispatch_queue(cd,1 - cd->curr);
+        
+        cd->curr = 1 - cd->curr;
+        // Return 1 if you have dispatched requests
+        return (ret1 || ret2);      
+}
+
+static void 
+cscan_add_request(struct request_queue *q, struct request *rq) {
+        struct CSCAN_data * cd = q->elevator->elevator_data;
+        struct CSCAN_request * crq = (struct CSCAN_request*)rq->elevator_private;
+
+        crq->rb_key = rq_rb_key(crq->request);
+        
+        if(rq->sector > cd->last_sector) {
+                crq->queue_id = cd->curr;
+                cscan_add_crq_rb(cd,crq); 
+        } else {
+                crq->queue_id = 1 - cd->curr;
+                cscan_add_crq_rb(cd,crq); 
+        }
+
+        if(rq_mergeable(rq)) {
+                cscan_add_crq_hash(cd,crq);
+
+                if(!q->last_merge)
+                        q->last_merge = rq;    
+        }                
+}
+/*
+ * See if we can find a request that this buffer can be coalesced with.
+ */
+int cscan_merge(request_queue_t *q, struct request **req,
+			struct bio *bio)
+{
+        struct CSCAN_data * cd = q->elevator->elevator_data;
+        struct request * __rq;
+        int ret;
+        sector_t rb_key;
+
+         /*
+         * try last_merge to avoid going to hash
+         */
+        ret = elv_try_last_merge(q, bio);
+        if (ret != ELEVATOR_NO_MERGE) {
+                __rq = q->last_merge;
+                goto out_insert;
+        }
+        /*
+         * see if the merge hash can satisfy a back merge
+         */
+        __rq = cscan_find_rq_hash(cd, bio->bi_sector);
+        if (__rq) {
+                BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
+
+                if (elv_rq_merge_ok(__rq, bio)) {
+                        ret = ELEVATOR_BACK_MERGE;
+                        goto out;
+                }
+        }
+
+         /*
+         * check for front merge
+         */
+         rb_key = bio->bi_sector + bio_sectors(bio);
+
+         __rq = cscan_find_crq_rb(cd, rb_key);
+         if (__rq) {
+                 BUG_ON(rb_key != rq_rb_key(__rq));
+
+                 if (elv_rq_merge_ok(__rq, bio)) {
+                         ret = ELEVATOR_FRONT_MERGE;
+                         goto out;
+                 }
+         }
+         return ELEVATOR_NO_MERGE;
+out:
+        q->last_merge = __rq;
+
+out_insert: 
+        *req = __rq;
+	return ret;
+}
+
+void cscan_merged_requests(request_queue_t *q, struct request *req,
+				  struct request *next)
+{
+        struct CSCAN_data * cd      = q->elevator->elevator_data;
+        struct CSCAN_request *crq   = 
+                        (struct CSCAN_request*)req->elevator_private;
+        struct CSCAN_request *tnext = 
+                        (struct CSCAN_request*)req->elevator_private;
+
+
+        BUG_ON(!crq);
+        BUG_ON(!tnext);
+        
+        cscan_del_crq_hash(crq);
+        cscan_add_crq_hash(cd,crq);
+        
+        if(rq_rb_key(req) |= crq->rb_key) {
+                cscan_del_crq_rb(cd,crq);
+                cscan_add_crq_rb(cd,crq);
+        }
+
+        cscan_remove_request(cd,tnext,tnext->queue_id);
+}
+
+void cscan_insert_request(request_queue_t *q, struct request *rq,
+			       int where)
+{
+        struct CSCAN_data * cd = q->elevator->elevator_data;
+
+        if (unlikely(rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)
+                        && where == ELEVATOR_INSERT_SORT))
+                where = ELEVATOR_INSERT_BACK;
+
+        switch (where) {
+                case ELEVATOR_INSERT_BACK:
+                        while (cscan_dispatch_requests(cd))
+                                ;
+                        list_add_tail(&rq->queuelist, cd->dispatch);
+                        break;
+                case ELEVATOR_INSERT_FRONT:
+                        list_add(&rq->queuelist, cd->dispatch);
+                        break;
+                case ELEVATOR_INSERT_SORT:
+                        BUG_ON(!blk_fs_request(rq));
+                        cscan_add_request(q, rq);
+                        break;
+                default:
+                        printk("%s: bad insert point %d\n", __FUNCTION__,where);
+                        return;
+        }
+
+                
+}
+
+static struct request *cscan_next_request(request_queue_t *q)
+{
+        struct CSCAN_data * cd = q->elevator->elevator_data;
+        struct request * rq = NULL;        
+
+	if (!list_empty(cd->dispatch)) {
+dispatch:       rq = list_entry_rq(cd->dispatch->next);
+                cd->last_sector = rq->sector + rq->nr_sectors;
+                return rq;
+        }                
+        if(cscan_dispatch_requests(cd)) {
+                goto dispatch;
+        }
+	return NULL;
+}
+
+static void
+cscan_put_request(request_queue_t *q, struct request *rq) 
+{
+        struct CSCAN_data * cd = q->elevator->elevator_data;
+        struct CSCAN_request * crq = 
+                        (struct CSCAN_request*)rq->elevator_private;
+
+        if(crq) {
+                mempool_free(crq,cd->crq_pool);
+                rq->elevator_private = NULL;
+        }
+}
+
+static int
+cscan_set_request(request_queue_t *q, struct request *rq,int 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;                
+                
+                INIT_LIST_HEAD(&crq->hash);
+                crq->on_hash = 0;
+
+                crq->request  = rq;
+                rq->elevator_private = crq;
+                return 0;
+       }
+       return 1;
+}
+
+static void 
+cscan_exit_queue(elevator_t * e) 
+{
+        struct CSCAN_data *cd = e->elevator_data;
+        mempool_destroy(cd->crq_pool);
+        kfree(cd->hash);
+        kfree(cd);
+}
+
+static int 
+cscan_init_queue(request_queue_t *q, elevator_t *e) 
+{
+       struct CSCAN_data * cd;
+       int i;
+
+       cd = kmalloc(sizeof(*cd),GFP_KERNEL);
+       if(!cd)
+                return -ENOMEM;
+       memset(cd,0,sizeof(*cd));
+       cd->sort_list[0] = RB_ROOT;
+       cd->sort_list[1] = RB_ROOT;
+       cd->count[0] = 0;
+       cd->count[1] = 0;
+      
+       cd->hash = kmalloc(sizeof(struct list_head)*DL_HASH_ENTRIES,GFP_KERNEL);
+
+       if(!cd->hash) {
+                kfree(cd);
+                return -ENOMEM;
+       }
+
+       for(i = 0;i< DL_HASH_ENTRIES; i++)
+                INIT_LIST_HEAD(&cd->hash[i]);
+        
+       cd->crq_pool = mempool_create(BLKDEV_MIN_RQ,mempool_alloc_slab,
+                        mempool_free_slab,crq_pool);
+       
+       if(!cd->crq_pool) {
+                kfree(cd->hash);
+                kfree(cd);
+                return -ENOMEM;
+       }
+
+       cd->dispatch = &q->queue_head;
+       cd->curr = 0;        
+       e->elevator_data = cd; 
+       return 0;
+}
+
+static struct elevator_type cscan = {
+	.ops = {
+		.elevator_merge_fn		= cscan_merge,
+		.elevator_merge_req_fn		= cscan_merged_requests,
+		.elevator_next_req_fn		= cscan_next_request,
+		.elevator_add_req_fn		= cscan_insert_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,
+};
+
+int cscan_init(void)
+{
+        int ret;
+        
+        crq_pool = kmem_cache_create("t_crq",sizeof(struct CSCAN_request),0,0,
+                NULL,NULL);
+        
+        if(!crq_pool)
+                return -ENOMEM;
+        
+        ret = elv_register(&cscan);
+        if(ret)
+                kmem_cache_destroy(crq_pool);
+        
+	return ret;
+}
+
+void cscan_exit(void)
+{
+        kmem_cache_destroy(crq_pool);
+	elv_unregister(&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.10/drivers/block/elevator.c linux-2.6.10-cscan/drivers/block/elevator.c
--- linux-2.6.10/drivers/block/elevator.c	2004-12-24 16:35:24.000000000 -0500
+++ linux-2.6.10-cscan/drivers/block/elevator.c	2006-03-30 21:34:33.000000000 -0500
@@ -161,6 +161,8 @@
 
 #if defined(CONFIG_IOSCHED_AS)
 	strcpy(chosen_elevator, "anticipatory");
+#elif defined(CONFIG_IOSCHED_CSCAN)
+	strcpy(chosen_elevator, "cscan");
 #elif defined(CONFIG_IOSCHED_DEADLINE)
 	strcpy(chosen_elevator, "deadline");
 #elif defined(CONFIG_IOSCHED_CFQ)
diff -urN linux-2.6.10/drivers/block/Kconfig.iosched linux-2.6.10-cscan/drivers/block/Kconfig.iosched
--- linux-2.6.10/drivers/block/Kconfig.iosched	2004-12-24 16:33:51.000000000 -0500
+++ linux-2.6.10-cscan/drivers/block/Kconfig.iosched	2006-03-30 21:34:40.000000000 -0500
@@ -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.10/drivers/block/Makefile linux-2.6.10-cscan/drivers/block/Makefile
--- linux-2.6.10/drivers/block/Makefile	2004-12-24 16:35:24.000000000 -0500
+++ linux-2.6.10-cscan/drivers/block/Makefile	2006-03-30 21:34:46.000000000 -0500
@@ -16,6 +16,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

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Matt Heler]

Any chance you can diff this against the latest 2.6 kernel ? 2.6.10 is abit 
old.

Thanks

On Thursday 30 March 2006 10:58 pm, 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.
>
> - Vishal
>
> PS: Please note that I have not subscribed to the LKML. For comments
> please reply back to this email.
>
> --
> Every passing minute is another chance to turn it all around.

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Vishal Patil]

I will post a patch for the 2.6.16 kernel over this weekend.

- Vishal

On 3/31/06, Matt Heler <lkml@lpbproductions.com> wrote:
> Any chance you can diff this against the latest 2.6 kernel ? 2.6.10 is abit
> old.
>
> Thanks
>
> On Thursday 30 March 2006 10:58 pm, 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.
> >
> > - Vishal
> >
> > PS: Please note that I have not subscribed to the LKML. For comments
> > please reply back to this email.
> >
> > --
> > Every passing minute is another chance to turn it all around.
>


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

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Bill Davidsen]

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.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Vishal Patil]

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.
>
> --
>     -bill davidsen (davidsen@tmr.com)
> "The secret to procrastination is to put things off until the
>   last possible moment - but no longer"  -me
>


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

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Jens Axboe]

On Tue, Apr 04 2006, Bill Davidsen 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.

Then it wouldn't be CSCAN, now would it? :-)

-- 
Jens Axboe

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Antonio Vargas]

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.

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Vishal Patil]

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.

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Vishal Patil]

[-- 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

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Jan Engelhardt]

>I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.

Thanks, I will try this.

I have a question, why does not it use the kernel's rbtree implementation?



Jan Engelhardt
-- 

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Jens Axboe]

On Tue, Apr 11 2006, Jan Engelhardt wrote:
> 
> >I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.
> 
> Thanks, I will try this.
> 
> I have a question, why does not it use the kernel's rbtree implementation?

It does, I dunno why you think it doesn't?

-- 
Jens Axboe

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Jan Engelhardt]

>> >I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.
>> 
>> Thanks, I will try this.
>> 
>> I have a question, why does not it use the kernel's rbtree implementation?
>
>It does, I dunno why you think it doesn't?

My bad. I thought because a function is named
  static struct cscan_request *__rb_insert_request
led me to believe this is the main insert function (when in fact it 
rb_link_node is). Maybe it should be just 
called "insert_request".

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Jens Axboe]

On Tue, Apr 11 2006, Jan Engelhardt wrote:
> >> >I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.
> >> 
> >> Thanks, I will try this.
> >> 
> >> I have a question, why does not it use the kernel's rbtree implementation?
> >
> >It does, I dunno why you think it doesn't?
> 
> My bad. I thought because a function is named
>   static struct cscan_request *__rb_insert_request
> led me to believe this is the main insert function (when in fact it 
> rb_link_node is). Maybe it should be just 
> called "insert_request".

It's an rb helper, it actually follows how the other io schedulers are
written as well.

-- 
Jens Axboe

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Vishal Patil]

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

Jan

I am attaching a final CSCAN scheduler patch for the 2.6.16.2 kernel.
The earlier patch that I had posted had a bug in the
"cscan_merged_requests" function. This has been taken care of in the
attached patch.  I would really appreciate if some one could help me
in conducting performance tests for the attached patch.

Many thanks for to all of you all for your inputs on this.

- Vishal


On 4/11/06, Jan Engelhardt <jengelh@linux01.gwdg.de> wrote:
> >> >I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.
> >>
> >> Thanks, I will try this.
> >>
> >> I have a question, why does not it use the kernel's rbtree implementation?
> >
> >It does, I dunno why you think it doesn't?
>
> My bad. I thought because a function is named
>   static struct cscan_request *__rb_insert_request
> led me to believe this is the main insert function (when in fact it
> rb_link_node is). Maybe it should be just
> called "insert_request".
>
>
>


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

[-- Attachment #2: cscan-2.6.16.2-patch --]
[-- Type: application/octet-stream, Size: 11603 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(next);
+
+        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

Re: CSCAN I/O scheduler for 2.6.10 kernel

[Jan Engelhardt]

>Jan
>
>I am attaching a final CSCAN scheduler patch for the 2.6.16.2 kernel.
>The earlier patch that I had posted had a bug in the
>"cscan_merged_requests" function. This has been taken care of in the
>attached patch.  I would really appreciate if some one could help me
>in conducting performance tests for the attached patch.
>
>Many thanks for to all of you all for your inputs on this.

Looks good, and did not break so far.
At frst I was puzzled why it did not show up in menuconfig, and eventually 
I found out it was not assigned a name. Also allow building it as a module. 
Updated patch for the Kconfig.iosched file in block is below.

diff -Ndpru linux-2.6.17-rc1~/block/Kconfig.iosched linux-2.6.17-rc1-csc/block/Kconfig.iosched
--- linux-2.6.17-rc1~/block/Kconfig.iosched	2006-04-03 05:22:10.000000000 +0200
+++ linux-2.6.17-rc1-csc/block/Kconfig.iosched	2006-04-13 13:12:09.275805000 +0200
@@ -38,6 +38,19 @@ config IOSCHED_CFQ
 	  among all processes in the system. It should provide a fair
 	  working environment, suitable for desktop systems.
 
+config IOSCHED_CSCAN
+	tristate "CSCAN I/O scheduler"
+	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
+
 choice
 	prompt "Default I/O scheduler"
 	default DEFAULT_AS
@@ -54,6 +67,9 @@ choice
 	config DEFAULT_CFQ
 		bool "CFQ" if IOSCHED_CFQ=y
 
+	config DEFAULT_CSCAN
+		bool "CSCAN" if IOSCHED_CSCAN=y
+
 	config DEFAULT_NOOP
 		bool "No-op"
 
@@ -64,6 +80,7 @@ config DEFAULT_IOSCHED
 	default "anticipatory" if DEFAULT_AS
 	default "deadline" if DEFAULT_DEADLINE
 	default "cfq" if DEFAULT_CFQ
+	default "cscan" if DEFAULT_CSCAN
 	default "noop" if DEFAULT_NOOP
 
 endmenu
#<<eof>>


Jan Engelhardt
--