cfq-iosched: add hlist for browsing parallel to the radix tree
Jens Axboe [Tue, 19 Feb 2008 09:02:29 +0000 (10:02 +0100)]
It's cumbersome to browse a radix tree from start to finish, especially
since we modify keys when a process exits. So add a hlist for the single
purpose of browsing over all known cfq_io_contexts, used for exit,
io prio change, etc.

This fixes http://bugzilla.kernel.org/show_bug.cgi?id=9948

Signed-off-by: Jens Axboe <jens.axboe@oracle.com>

block/blk-ioc.c
block/cfq-iosched.c
include/linux/iocontext.h

index 4ae0929..e34df7c 100644 (file)
@@ -17,17 +17,13 @@ static struct kmem_cache *iocontext_cachep;
 
 static void cfq_dtor(struct io_context *ioc)
 {
-       struct cfq_io_context *cic[1];
-       int r;
+       if (!hlist_empty(&ioc->cic_list)) {
+               struct cfq_io_context *cic;
 
-       /*
-        * We don't have a specific key to lookup with, so use the gang
-        * lookup to just retrieve the first item stored. The cfq exit
-        * function will iterate the full tree, so any member will do.
-        */
-       r = radix_tree_gang_lookup(&ioc->radix_root, (void **) cic, 0, 1);
-       if (r > 0)
-               cic[0]->dtor(ioc);
+               cic = list_entry(ioc->cic_list.first, struct cfq_io_context,
+                                                               cic_list);
+               cic->dtor(ioc);
+       }
 }
 
 /*
@@ -57,18 +53,16 @@ EXPORT_SYMBOL(put_io_context);
 
 static void cfq_exit(struct io_context *ioc)
 {
-       struct cfq_io_context *cic[1];
-       int r;
-
        rcu_read_lock();
-       /*
-        * See comment for cfq_dtor()
-        */
-       r = radix_tree_gang_lookup(&ioc->radix_root, (void **) cic, 0, 1);
-       rcu_read_unlock();
 
-       if (r > 0)
-               cic[0]->exit(ioc);
+       if (!hlist_empty(&ioc->cic_list)) {
+               struct cfq_io_context *cic;
+
+               cic = list_entry(ioc->cic_list.first, struct cfq_io_context,
+                                                               cic_list);
+               cic->exit(ioc);
+       }
+       rcu_read_unlock();
 }
 
 /* Called by the exitting task */
@@ -105,6 +99,7 @@ struct io_context *alloc_io_context(gfp_t gfp_flags, int node)
                ret->nr_batch_requests = 0; /* because this is 0 */
                ret->aic = NULL;
                INIT_RADIX_TREE(&ret->radix_root, GFP_ATOMIC | __GFP_HIGH);
+               INIT_HLIST_HEAD(&ret->cic_list);
                ret->ioc_data = NULL;
        }
 
index ca198e6..0f962ec 100644 (file)
@@ -1145,38 +1145,19 @@ static void cfq_put_queue(struct cfq_queue *cfqq)
 /*
  * Call func for each cic attached to this ioc. Returns number of cic's seen.
  */
-#define CIC_GANG_NR    16
 static unsigned int
 call_for_each_cic(struct io_context *ioc,
                  void (*func)(struct io_context *, struct cfq_io_context *))
 {
-       struct cfq_io_context *cics[CIC_GANG_NR];
-       unsigned long index = 0;
-       unsigned int called = 0;
-       int nr;
+       struct cfq_io_context *cic;
+       struct hlist_node *n;
+       int called = 0;
 
        rcu_read_lock();
-
-       do {
-               int i;
-
-               /*
-                * Perhaps there's a better way - this just gang lookups from
-                * 0 to the end, restarting after each CIC_GANG_NR from the
-                * last key + 1.
-                */
-               nr = radix_tree_gang_lookup(&ioc->radix_root, (void **) cics,
-                                               index, CIC_GANG_NR);
-               if (!nr)
-                       break;
-
-               called += nr;
-               index = 1 + (unsigned long) cics[nr - 1]->key;
-
-               for (i = 0; i < nr; i++)
-                       func(ioc, cics[i]);
-       } while (nr == CIC_GANG_NR);
-
+       hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list) {
+               func(ioc, cic);
+               called++;
+       }
        rcu_read_unlock();
 
        return called;
@@ -1190,6 +1171,7 @@ static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
 
        spin_lock_irqsave(&ioc->lock, flags);
        radix_tree_delete(&ioc->radix_root, cic->dead_key);
+       hlist_del_rcu(&cic->cic_list);
        spin_unlock_irqrestore(&ioc->lock, flags);
 
        kmem_cache_free(cfq_ioc_pool, cic);
@@ -1280,6 +1262,7 @@ cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
        if (cic) {
                cic->last_end_request = jiffies;
                INIT_LIST_HEAD(&cic->queue_list);
+               INIT_HLIST_NODE(&cic->cic_list);
                cic->dtor = cfq_free_io_context;
                cic->exit = cfq_exit_io_context;
                elv_ioc_count_inc(ioc_count);
@@ -1501,6 +1484,7 @@ cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
                rcu_assign_pointer(ioc->ioc_data, NULL);
 
        radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
+       hlist_del_rcu(&cic->cic_list);
        spin_unlock_irqrestore(&ioc->lock, flags);
 
        cfq_cic_free(cic);
@@ -1561,6 +1545,8 @@ static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
                spin_lock_irqsave(&ioc->lock, flags);
                ret = radix_tree_insert(&ioc->radix_root,
                                                (unsigned long) cfqd, cic);
+               if (!ret)
+                       hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
                spin_unlock_irqrestore(&ioc->lock, flags);
 
                radix_tree_preload_end();
index 593b222..1b4ccf2 100644 (file)
@@ -50,6 +50,7 @@ struct cfq_io_context {
        sector_t seek_mean;
 
        struct list_head queue_list;
+       struct hlist_node cic_list;
 
        void (*dtor)(struct io_context *); /* destructor */
        void (*exit)(struct io_context *); /* called on task exit */
@@ -77,6 +78,7 @@ struct io_context {
 
        struct as_io_context *aic;
        struct radix_tree_root radix_root;
+       struct hlist_head cic_list;
        void *ioc_data;
 };