blkcg: use radix tree to index blkgs from blkcg
authorTejun Heo <tj@kernel.org>
Thu, 19 Apr 2012 23:29:24 +0000 (16:29 -0700)
committerJens Axboe <axboe@kernel.dk>
Fri, 20 Apr 2012 08:06:40 +0000 (10:06 +0200)
commita637120e49021d197e9578cba545bbaa459cbb51
tree0d502a8fcc55c89eb4d79a7578e46a9273d1f2c8
parent496fb7806d616185a46865a4f3a20ef19dc6c7e3
blkcg: use radix tree to index blkgs from blkcg

blkg lookup is currently performed by traversing linked list anchored
at blkcg->blkg_list.  This is very unscalable and with blk-throttle
enabled and enough request queues on the system, this can get very
ugly quickly (blk-throttle performs look up on every bio submission).

This patch makes blkcg use radix tree to index blkgs combined with
simple last-looked-up hint.  This is mostly identical to how icqs are
indexed from ioc.

Note that because __blkg_lookup() may be invoked without holding queue
lock, hint is only updated from __blkg_lookup_create().  Due to cfq's
cfqq caching, this makes hint updates overly lazy.  This will be
improved with scheduled blkcg aware request allocation.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Vivek Goyal <vgoyal@redhat.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
block/blk-cgroup.c
block/blk-cgroup.h