Skip to contentSkip to conversation

CSCAN I/O scheduler for 2.6.10 kernel

PATCH Vishal Patil 6 participants 15 messages Mar 31, 2006 – Apr 13, 2006 1 message not in the archive Block layer

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

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.

drivers/block/cscan.c +512 -0
diff -urN linux-2.6.10/drivers/block/cscan.c linux-2.6.10-cscan/drivers/block/cscan.c
@@ -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");
drivers/block/elevator.c +2 -0
diff -urN linux-2.6.10/drivers/block/elevator.c linux-2.6.10-cscan/drivers/block/elevator.c
@@ -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)
drivers/block/Kconfig.iosched +13 -0
diff -urN linux-2.6.10/drivers/block/Kconfig.iosched linux-2.6.10-cscan/drivers/block/Kconfig.iosched
@@ -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
drivers/block/Makefile +1 -0
diff -urN linux-2.6.10/drivers/block/Makefile linux-2.6.10-cscan/drivers/block/Makefile
@@ -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
#2 lore raw

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

Thanks

Quoted 17 lines · Vishal Patil

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.

#3 lore raw

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

- Vishal

Quoted 24 lines · Matt Heler

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

Thanks

Quoted 17 lines · Vishal Patil

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.

#4 lore raw
In reply to Vishal Patil
Quoted 10 lines · Vishal Patil

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.

Signature · 3 lines
   -bill davidsen ([email protected])
"The secret to procrastination is to put things off until the
 last possible moment - but no longer"  -me
#5 lore raw

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

Quoted 11 lines · Bill Davidsen
Quoted 10 lines · Vishal Patil

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.

Quoted 9 lines

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 ([email protected])
"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.

#6 lore raw
Quoted 21 lines · 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

Quoted 15 lines · Bill Davidsen
Quoted 10 lines · Vishal Patil

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/
[email protected]
[email protected]

Every day, every year
you have to work
you have to study
you have to scene.

#7 lore raw

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

Quoted 32 lines · Antonio Vargas
Quoted 21 lines · 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

Quoted 15 lines · Bill Davidsen
Quoted 10 lines · Vishal Patil

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

Quoted 9 lines

http://wind.codepixel.com/
[email protected]
[email protected]

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.

#8 lore raw

I am attaching the CSCAN scheduler patch for 2.6.16.2 kernel.

- Vishal

Quoted 69 lines · 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

Quoted 32 lines · Antonio Vargas
Quoted 21 lines · 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

Quoted 15 lines · Bill Davidsen
Quoted 10 lines · Vishal Patil

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

Quoted 9 lines

http://wind.codepixel.com/
[email protected]
[email protected]

Every day, every year
you have to work
you have to study
you have to scene.

Quoted 3 lines

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

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

#9 lore raw
Quoted 2 lines

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

#10 lore raw
Quoted 6 lines · Jan Engelhardt
Quoted 2 lines

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?

Signature · 1 line
Jens Axboe
#11 lore raw
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

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".

#12 lore raw
Quoted 6 lines · Jan Engelhardt
Quoted 6 lines
Quoted 5 lines
Quoted 1 line

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?

Quoted 7 lines
Quoted 1 line

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.

Signature · 1 line
Jens Axboe
#13 lore raw
In reply to 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.

- Vishal

Quoted 6 lines · Jan Engelhardt
Quoted 6 lines
Quoted 5 lines
Quoted 1 line

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?

Quoted 10 lines
Quoted 1 line

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.

#14 lore raw
Quoted 9 lines

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.

block/Kconfig.iosched +17 -0
diff -Ndpru linux-2.6.17-rc1~/block/Kconfig.iosched linux-2.6.17-rc1-csc/block/Kconfig.iosched
@@ -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

#15 lore raw
In reply to Bill Davidsen
Quoted 11 lines · Bill Davidsen
Quoted 10 lines · Vishal Patil

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.

Quoted 3 lines

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? :-)

Signature · 1 line
Jens Axboe