1 diff -uprN linux-2.6.28.orig/block/bfq-ioc.c linux-2.6.28.new/block/bfq-ioc.c
2 --- linux-2.6.28.orig/block/bfq-ioc.c 2011-06-11 08:27:30.326116630 +0200
3 +++ linux-2.6.28.new/block/bfq-ioc.c 2011-06-11 08:57:12.535863444 +0200
4 @@ -55,10 +55,11 @@ static void cic_free_func(struct io_cont
8 - BUG_ON(cic->dead_key == 0);
9 + BUG_ON(!(cic->dead_key & CIC_DEAD_KEY));
11 spin_lock_irqsave(&ioc->lock, flags);
12 - radix_tree_delete(&ioc->bfq_radix_root, cic->dead_key);
13 + radix_tree_delete(&ioc->bfq_radix_root,
14 + cic->dead_key >> CIC_DEAD_INDEX_SHIFT);
15 hlist_del_init_rcu(&cic->cic_list);
16 spin_unlock_irqrestore(&ioc->lock, flags);
18 @@ -83,9 +84,7 @@ static void bfq_free_io_context(struct i
20 * Whenever no more tasks are using @cic or @bfqd is deallocated we
21 * need to invalidate its entry in the radix tree hash table and to
22 - * release the queues it refers to. Save the key used for insertion
23 - * in @cic->dead_key to remove @cic from the radix tree later and assign
24 - * %NULL to its search key to prevent future lookups to succeed on it.
25 + * release the queues it refers to.
27 * Called under the queue lock.
29 @@ -99,7 +98,7 @@ static void __bfq_exit_single_io_context
31 * Make sure key == NULL is seen for dead queues.
33 - cic->dead_key = (unsigned long)cic->key;
34 + cic->dead_key = bfqd_dead_key(bfqd);
37 rcu_assign_pointer(cic->key, NULL);
38 @@ -190,6 +189,7 @@ static void bfq_drop_dead_cic(struct bfq
41 WARN_ON(!list_empty(&cic->queue_list));
42 + BUG_ON(cic->dead_key != bfqd_dead_key(bfqd));
44 spin_lock_irqsave(&ioc->lock, flags);
46 @@ -203,7 +203,7 @@ static void bfq_drop_dead_cic(struct bfq
49 if (!hlist_unhashed(&cic->cic_list)) {
50 - radix_tree_delete(&ioc->bfq_radix_root, (unsigned long)bfqd);
51 + radix_tree_delete(&ioc->bfq_radix_root, bfqd->cic_index);
52 hlist_del_init_rcu(&cic->cic_list);
55 @@ -241,7 +241,7 @@ static struct cfq_io_context *bfq_cic_lo
58 cic = radix_tree_lookup(&ioc->bfq_radix_root,
59 - (unsigned long)bfqd);
64 @@ -292,7 +292,7 @@ static int bfq_cic_link(struct bfq_data
66 spin_lock_irqsave(&ioc->lock, flags);
67 ret = radix_tree_insert(&ioc->bfq_radix_root,
68 - (unsigned long)bfqd, cic);
69 + bfqd->cic_index, cic);
71 hlist_add_head_rcu(&cic->cic_list, &ioc->bfq_cic_list);
72 spin_unlock_irqrestore(&ioc->lock, flags);
73 diff -uprN linux-2.6.28.orig/block/bfq-iosched.c linux-2.6.28.new/block/bfq-iosched.c
74 --- linux-2.6.28.orig/block/bfq-iosched.c 2011-06-11 08:57:33.541762649 +0200
75 +++ linux-2.6.28.new/block/bfq-iosched.c 2011-06-11 08:57:12.543862653 +0200
77 #include <linux/elevator.h>
78 #include <linux/rbtree.h>
79 #include <linux/ioprio.h>
80 +#include <linux/idr.h>
83 /* Max number of dispatches in one round of service. */
84 @@ -98,6 +99,9 @@ static DEFINE_PER_CPU(unsigned long, bfq
85 static struct completion *bfq_ioc_gone;
86 static DEFINE_SPINLOCK(bfq_ioc_gone_lock);
88 +static DEFINE_SPINLOCK(cic_index_lock);
89 +static DEFINE_IDA(cic_index_ida);
91 /* Below this threshold (in ms), we consider thinktime immediate. */
94 @@ -1983,6 +1987,10 @@ static void bfq_exit_queue(struct elevat
96 bfq_shutdown_timer_wq(bfqd);
98 + spin_lock(&cic_index_lock);
99 + ida_remove(&cic_index_ida, bfqd->cic_index);
100 + spin_unlock(&cic_index_lock);
102 /* Wait for cic->key accessors to exit their grace periods. */
105 @@ -1992,15 +2000,40 @@ static void bfq_exit_queue(struct elevat
109 +static int bfq_alloc_cic_index(void)
114 + if (!ida_pre_get(&cic_index_ida, GFP_KERNEL))
117 + spin_lock(&cic_index_lock);
118 + error = ida_get_new(&cic_index_ida, &index);
119 + spin_unlock(&cic_index_lock);
120 + if (error && error != -EAGAIN)
127 static void *bfq_init_queue(struct request_queue *q)
129 struct bfq_group *bfqg;
130 struct bfq_data *bfqd;
133 + i = bfq_alloc_cic_index();
137 bfqd = kmalloc_node(sizeof(*bfqd), GFP_KERNEL | __GFP_ZERO, q->node);
141 + bfqd->cic_index = i;
143 INIT_LIST_HEAD(&bfqd->cic_list);
146 @@ -2273,6 +2306,7 @@ static void __exit bfq_exit(void)
148 if (elv_ioc_count_read(bfq_ioc_count) != 0)
149 wait_for_completion(&all_gone);
150 + ida_destroy(&cic_index_ida);
154 diff -uprN linux-2.6.28.orig/block/bfq.h linux-2.6.28.new/block/bfq.h
155 --- linux-2.6.28.orig/block/bfq.h 2011-06-11 08:57:33.545762247 +0200
156 +++ linux-2.6.28.new/block/bfq.h 2011-06-11 08:57:12.543862653 +0200
157 @@ -195,6 +195,7 @@ struct bfq_group;
158 * @peak_rate: peak transfer rate observed for a budget.
159 * @peak_rate_samples: number of samples used to calculate @peak_rate.
160 * @bfq_max_budget: maximum budget allotted to a bfq_queue before rescheduling.
161 + * @cic_index: use small consequent indexes as radix tree keys to reduce depth
162 * @cic_list: list of all the cics active on the bfq_data device.
163 * @group_list: list of all the bfq_groups active on the device.
164 * @active_list: list of all the bfq_queues active on the device.
165 @@ -248,6 +249,7 @@ struct bfq_data {
167 unsigned long bfq_max_budget;
169 + unsigned int cic_index;
170 struct list_head cic_list;
171 struct hlist_head group_list;
172 struct list_head active_list;
173 @@ -495,6 +497,14 @@ static inline void call_for_each_cic(str
177 +#define CIC_DEAD_KEY 1ul
178 +#define CIC_DEAD_INDEX_SHIFT 1
180 +static inline unsigned long bfqd_dead_key(struct bfq_data *bfqd)
182 + return (unsigned long)(bfqd->cic_index << CIC_DEAD_INDEX_SHIFT | CIC_DEAD_KEY);
186 * bfq_get_bfqd_locked - get a lock to a bfqd using a RCU protected pointer.
187 * @ptr: a pointer to a bfqd.