[PATCH] rbtree core for io scheduler

This patch has a bunch of io scheduler goodies that are, by now, well
tested in -mm and by self and Nick Piggin. In order of interest:

- Use rbtree data structure for sorting of requests. Even with the
  default queue lengths that are fairly short, this cuts a lot of run
  time for io scheduler intensive work loads. If we go to longer queue
  lengths, it very quickly becomes a necessity.

- Add sysfs interface for the tunables. At the same time, finally kill
  the BLKELVGET/BLKELVSET completely. I made these return -ENOTTY in
  2.5.1, but there are left-overs around the kernel. This old interface
  was never any good, it was centered around just one io scheduler.

The io scheduler core itself has received count less hours of tuning by
myself and Nick, should be in pretty good shape. Please apply.

Andrew, I made some sysfs changes to the version from 2.5.56-mm1. It
didn't even compile without warnings (or work, for that matter), as the
sysfs store/show procedures needed updating. Hmm?

1 files changed, 11 insertions, 14 deletions

diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 62092e8ed2ad..8a9c22d3b16b 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -13,6 +13,7 @@ typedef struct request *(elevator_next_req_fn) (request_queue_t *);
 typedef void (elevator_add_req_fn) (request_queue_t *, struct request *, struct list_head *);
 typedef int (elevator_queue_empty_fn) (request_queue_t *);
 typedef void (elevator_remove_req_fn) (request_queue_t *, struct request *);
+typedef struct request *(elevator_request_list_fn) (request_queue_t *, struct request *);
 typedef struct list_head *(elevator_get_sort_head_fn) (request_queue_t *, struct request *);
 
 typedef int (elevator_init_fn) (request_queue_t *, elevator_t *);
@@ -29,12 +30,17 @@ struct elevator_s
 	elevator_remove_req_fn *elevator_remove_req_fn;
 
 	elevator_queue_empty_fn *elevator_queue_empty_fn;
-	elevator_get_sort_head_fn *elevator_get_sort_head_fn;
+
+	elevator_request_list_fn *elevator_former_req_fn;
+	elevator_request_list_fn *elevator_latter_req_fn;
 
 	elevator_init_fn *elevator_init_fn;
 	elevator_exit_fn *elevator_exit_fn;
 
 	void *elevator_data;
+
+	struct kobject kobj;
+	struct kobj_type *elevator_ktype;
 };
 
 /*
@@ -48,7 +54,10 @@ extern void elv_merge_requests(request_queue_t *, struct request *,
 extern void elv_merged_request(request_queue_t *, struct request *);
 extern void elv_remove_request(request_queue_t *, struct request *);
 extern int elv_queue_empty(request_queue_t *);
-extern inline struct list_head *elv_get_sort_head(request_queue_t *, struct request *);
+extern struct request *elv_former_request(request_queue_t *, struct request *);
+extern struct request *elv_latter_request(request_queue_t *, struct request *);
+extern int elv_register_queue(struct gendisk *);
+extern void elv_unregister_queue(struct gendisk *);
 
 #define __elv_add_request_pos(q, rq, pos)	\
 	(q)->elevator.elevator_add_req_fn((q), (rq), (pos))
@@ -64,18 +73,6 @@ extern elevator_t elevator_noop;
  */
 extern elevator_t iosched_deadline;
 
-/*
- * use the /proc/iosched interface, all the below is history ->
- */
-typedef struct blkelv_ioctl_arg_s {
-	int queue_ID;
-	int read_latency;
-	int write_latency;
-	int max_bomb_segments;
-} blkelv_ioctl_arg_t;
-#define BLKELVGET   _IOR(0x12,106,sizeof(blkelv_ioctl_arg_t))
-#define BLKELVSET   _IOW(0x12,107,sizeof(blkelv_ioctl_arg_t))
-
 extern int elevator_init(request_queue_t *, elevator_t *);
 extern void elevator_exit(request_queue_t *);
 extern inline int bio_rq_in_between(struct bio *, struct request *, struct list_head *);