Messages in this thread | | | Date | Wed, 8 Apr 2009 21:18:59 +0200 | Subject | Re: SSD and IO schedulers | From | Corrado Zoccolo <> |
| |
Hi, I found that elevator=deadline performs much better than noop for writes, and almost as well for reads, and started to wonder how a combination of noop (for read) + deadline (for write) would work in practice (since deadline still doesn't support the automatic ssd detection). I developed a simple hybrid scheduler (see attached), that implements this idea, and it saved 1 s of my boot time compared to all other schedulers (cfq, deadline and noop, each loses on some part of the workload), that is a mixed read write workload, with writes that go mainly to a very slow device (SDHC card, where I mount /var).
This proof of concept still doesn't support priorities, but I'm willing to add them at least for read, in which the latency for sync-reads could be improved.
Corrado
On Sat, Feb 7, 2009 at 6:58 PM, Jan Knutar <jk-lkml@sci.fi> wrote: > On Wednesday 04 February 2009, J.A. Magallón wrote: > >> Perhaps the reason is that, as the SSD is not so good, it behaves >> more like a rotational drive ;). > > Do any other SSDs except Intel's exist that DON'T behave more like a > rotational drive? I am guessing using something like LogFS would give > the biggest boost on cheap SSDs and all memory cards. > -- > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > Please read the FAQ at http://www.tux.org/lkml/ >
-- __________________________________________________________________________
dott. Corrado Zoccolo mailto:czoccolo@gmail.com PhD - Department of Computer Science - University of Pisa, Italy -------------------------------------------------------------------------- The self-confidence of a warrior is not the self-confidence of the average man. The average man seeks certainty in the eyes of the onlooker and calls that self-confidence. The warrior seeks impeccability in his own eyes and calls that humbleness. Tales of Power - C. Castaneda /* -*- mode:C; tab-width:8; c-basic-offset:8 -*- * Ssd i/o scheduler. * * Copyright (C) 2002 Jens Axboe <axboe@kernel.dk> */ #include <linux/kernel.h> #include <linux/fs.h> #include <linux/blkdev.h> #include <linux/elevator.h> #include <linux/bio.h> #include <linux/module.h> #include <linux/slab.h> #include <linux/init.h> #include <linux/compiler.h> #include <linux/rbtree.h>
/* * See Documentation/block/ssd-iosched.txt */ static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */ static const int writes_starved = 2; /* max times reads can starve a write */ static const int fifo_batch = 16; /* # of sequential requests treated as one by the above parameters. For throughput. */
struct ssd_data { /* * run time data */
/* * requests (ssd_rq s) are present on both sort_list and fifo_list */ /* for read */ struct list_head read_queue;
/* for write */ struct rb_root sort_list_write; struct list_head fifo_list_write;
/* * next in sort order. read, write or both are NULL */ struct request *next_rq_write;
/* stats */ unsigned int batching; /* number of sequential requests made */ sector_t last_sector; /* head position */ unsigned int starved; /* times reads have starved writes */
/* * settings that change how the i/o scheduler behaves */ int fifo_expire_write; int fifo_batch; int writes_starved; };
static void ssd_move_write_request(struct ssd_data *, struct request *);
/* * get the request after `rq' in sector-sorted order */ static inline struct request * ssd_latter_write_request(struct request *rq) { struct rb_node *node = rb_next(&rq->rb_node);
if (node) return rb_entry_rq(node);
return NULL; }
static void ssd_add_write_rq_rb(struct ssd_data *dd, struct request *rq) { struct rb_root *root = &dd->sort_list_write; struct request *__alias;
while (unlikely(__alias = elv_rb_add(root, rq))) ssd_move_write_request(dd, __alias); }
static inline void ssd_del_write_rq_rb(struct ssd_data *dd, struct request *rq) { if (dd->next_rq_write == rq) dd->next_rq_write = ssd_latter_write_request(rq);
elv_rb_del(&dd->sort_list_write, rq); }
/* * add rq to rbtree and fifo */ static void ssd_add_request(struct request_queue *q, struct request *rq) { struct ssd_data *dd = q->elevator->elevator_data; const int data_dir = rq_data_dir(rq); if(data_dir==READ) { list_add_tail(&rq->queuelist, &dd->read_queue); } else { ssd_add_write_rq_rb(dd, rq);
/* * set expire time and add to fifo list */ rq_set_fifo_time(rq, jiffies + dd->fifo_expire_write); list_add_tail(&rq->queuelist, &dd->fifo_list_write); } }
/* * remove rq from rbtree and fifo. */ static void ssd_remove_write_request(struct request_queue *q, struct request *rq) { struct ssd_data *dd = q->elevator->elevator_data;
rq_fifo_clear(rq); ssd_del_write_rq_rb(dd, rq); }
static void ssd_merged_request(struct request_queue *q, struct request *req, int type) { struct ssd_data *dd = q->elevator->elevator_data;
/* * if the merge was a front merge, we need to reposition request */ if (type == ELEVATOR_FRONT_MERGE && rq_data_dir(req)==WRITE) { elv_rb_del(&dd->sort_list_write, req); ssd_add_write_rq_rb(dd, req); } }
static void ssd_merged_requests(struct request_queue *q, struct request *req, struct request *next) { if(rq_data_dir(req)==READ) { list_del_init(&next->queuelist); } else { /* * if next expires before rq, assign its expire time to rq * and move into next position (next will be deleted) in fifo */ if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) { if (time_before(rq_fifo_time(next), rq_fifo_time(req))) { list_move(&req->queuelist, &next->queuelist); rq_set_fifo_time(req, rq_fifo_time(next)); } }
/* * kill knowledge of next, this one is a goner */ ssd_remove_write_request(q, next); } }
/* * move request from sort list to dispatch queue. */ static inline void ssd_move_write_to_dispatch(struct ssd_data *dd, struct request *rq) { struct request_queue *q = rq->q;
ssd_remove_write_request(q, rq); elv_dispatch_add_tail(q, rq); }
/* * move an entry to dispatch queue */ static void ssd_move_write_request(struct ssd_data *dd, struct request *rq) { dd->next_rq_write = ssd_latter_write_request(rq); dd->last_sector = rq_end_sector(rq);
/* * take it off the sort and fifo list, move * to dispatch queue */ ssd_move_write_to_dispatch(dd, rq); }
/* * ssd_check_fifo_write returns 0 if there are no expired requests on the fifo, * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir]) */ static inline int ssd_check_fifo_write(struct ssd_data *dd) { struct request *rq = rq_entry_fifo(dd->fifo_list_write.next);
/* * rq is expired! */ if (time_after(jiffies, rq_fifo_time(rq))) return 1;
return 0; }
/* * ssd_dispatch_requests selects the best request according to * read/write expire, fifo_batch, etc */ static int ssd_dispatch_requests(struct request_queue *q, int force) { struct ssd_data *dd = q->elevator->elevator_data; const int reads = !list_empty(&dd->read_queue); const int writes = !list_empty(&dd->fifo_list_write); struct request *rq;
if (reads) { if (writes && (dd->starved++ >= dd->writes_starved)) goto dispatch_writes;
rq = list_entry(dd->read_queue.next, struct request, queuelist); list_del_init(&rq->queuelist); elv_dispatch_sort(q, rq); return 1; }
/* * batches are currently reads XOR writes */ if (dd->next_rq_write) rq = dd->next_rq_write;
if (rq && dd->batching < dd->fifo_batch) /* we have a next request are still entitled to batch */ goto dispatch_request;
/* * there are either no reads or writes have been starved */
if (writes) { dispatch_writes: BUG_ON(RB_EMPTY_ROOT(&dd->sort_list_write)); dd->starved = 0; goto dispatch_find_request; } return 0;
dispatch_find_request: /* * we are not running a batch, find best request for WRITE */ if (ssd_check_fifo_write(dd) || !dd->next_rq_write) { /* * A deadline has expired, the last request was in the other * direction, or we have run out of higher-sectored requests. * Start again from the request with the earliest expiry time. */ rq = rq_entry_fifo(dd->fifo_list_write.next); } else { /* * The last req was the same dir and we have a next request in * sort order. No expired requests so continue on from here. */ rq = dd->next_rq_write; }
dd->batching = 0;
dispatch_request: /* * rq is the selected appropriate request. */ dd->batching++; ssd_move_write_request(dd, rq);
return 1; }
static int ssd_queue_empty(struct request_queue *q) { struct ssd_data *dd = q->elevator->elevator_data;
return list_empty(&dd->fifo_list_write) && list_empty(&dd->read_queue); }
static struct request * ssd_former_request(struct request_queue *q, struct request *rq) { struct ssd_data *nd = q->elevator->elevator_data; const int data_dir = rq_data_dir(rq); if(data_dir==READ) { if (rq->queuelist.prev == &nd->read_queue) return NULL; return list_entry(rq->queuelist.prev, struct request, queuelist); } else { return elv_rb_former_request(q,rq); } }
static struct request * ssd_latter_request(struct request_queue *q, struct request *rq) { struct ssd_data *dd = q->elevator->elevator_data; const int data_dir = rq_data_dir(rq); if(data_dir==READ) { if (rq->queuelist.next == &dd->read_queue) return NULL; return list_entry(rq->queuelist.next, struct request, queuelist); } else { return elv_rb_latter_request(q,rq); } }
static void ssd_exit_queue(struct elevator_queue *e) { struct ssd_data *dd = e->elevator_data;
BUG_ON(!list_empty(&dd->read_queue)); BUG_ON(!list_empty(&dd->fifo_list_write));
kfree(dd); }
/* * initialize elevator private data (ssd_data). */ static void *ssd_init_queue(struct request_queue *q) { struct ssd_data *dd;
dd = kmalloc_node(sizeof(*dd), GFP_KERNEL | __GFP_ZERO, q->node); if (!dd) return NULL;
INIT_LIST_HEAD(&dd->read_queue); INIT_LIST_HEAD(&dd->fifo_list_write); dd->sort_list_write = RB_ROOT; dd->fifo_expire_write = write_expire; dd->writes_starved = writes_starved; dd->fifo_batch = fifo_batch; return dd; }
/* * sysfs parts below */
static ssize_t ssd_var_show(int var, char *page) { return sprintf(page, "%d\n", var); }
static ssize_t ssd_var_store(int *var, const char *page, size_t count) { char *p = (char *) page;
*var = simple_strtol(p, &p, 10); return count; }
#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \ static ssize_t __FUNC(struct elevator_queue *e, char *page) \ { \ struct ssd_data *dd = e->elevator_data; \ int __data = __VAR; \ if (__CONV) \ __data = jiffies_to_msecs(__data); \ return ssd_var_show(__data, (page)); \ } SHOW_FUNCTION(ssd_write_expire_show, dd->fifo_expire_write, 1); SHOW_FUNCTION(ssd_writes_starved_show, dd->writes_starved, 0); SHOW_FUNCTION(ssd_fifo_batch_show, dd->fifo_batch, 0); #undef SHOW_FUNCTION
#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \ { \ struct ssd_data *dd = e->elevator_data; \ int __data; \ int ret = ssd_var_store(&__data, (page), count); \ if (__data < (MIN)) \ __data = (MIN); \ else if (__data > (MAX)) \ __data = (MAX); \ if (__CONV) \ *(__PTR) = msecs_to_jiffies(__data); \ else \ *(__PTR) = __data; \ return ret; \ } STORE_FUNCTION(ssd_write_expire_store, &dd->fifo_expire_write, 0, INT_MAX, 1); STORE_FUNCTION(ssd_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0); STORE_FUNCTION(ssd_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0); #undef STORE_FUNCTION
#define DD_ATTR(name) \ __ATTR(name, S_IRUGO|S_IWUSR, ssd_##name##_show, \ ssd_##name##_store)
static struct elv_fs_entry ssd_attrs[] = { DD_ATTR(write_expire), DD_ATTR(writes_starved), DD_ATTR(fifo_batch), __ATTR_NULL };
static struct elevator_type iosched_ssd = { .ops = { .elevator_merged_fn = ssd_merged_request, .elevator_merge_req_fn = ssd_merged_requests, .elevator_dispatch_fn = ssd_dispatch_requests, .elevator_add_req_fn = ssd_add_request, .elevator_queue_empty_fn = ssd_queue_empty, .elevator_former_req_fn = ssd_former_request, .elevator_latter_req_fn = ssd_latter_request, .elevator_init_fn = ssd_init_queue, .elevator_exit_fn = ssd_exit_queue, },
.elevator_attrs = ssd_attrs, .elevator_name = "ssd", .elevator_owner = THIS_MODULE, };
static int __init ssd_init(void) { elv_register(&iosched_ssd);
return 0; }
static void __exit ssd_exit(void) { elv_unregister(&iosched_ssd); }
module_init(ssd_init); module_exit(ssd_exit);
MODULE_AUTHOR("Corrado Zoccolo"); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("ssd IO scheduler");
| |