RE: [PATCH] preview - block layer help to detect sequential IO

[Kashyap Desai]

> Hi, Kashyap,
>
> I'm CC-ing Kent, seeing how this is his code.

Hi Jeff and Kent, See my reply inline.

>
> Kashyap Desai  writes:
>
> > Objective of this patch is -
> >
> > To move code used in bcache module in block layer which is used to
> > find IO stream.  Reference code @drivers/md/bcache/request.c
> > check_should_bypass().  This is a high level patch for review and
> > understand if it is worth to follow ?
> >
> > As of now bcache module use this logic, but good to have it in block
> > layer and expose function for external use.
> >
> > In this patch, I move logic of sequential IO search in block layer and
> > exposed function blk_queue_rq_seq_cutoff.  Low level driver just need
> > to call if they want stream detection per request queue.  For my
> > testing I just added call blk_queue_rq_seq_cutoff(sdev->request_queue,
> > 4) megaraid_sas driver.
> >
> > In general, code of bcache module was referred and they are doing
> > almost same as what we want to do in megaraid_sas driver below patch -
> >
> > http://marc.info/?l=linux-scsi=148245616108288=2
> >
> > bcache implementation use search algorithm (hashed based on bio start
> > sector) and detects 128 streams.  wanted those implementation
> > to skip sequential IO to be placed on SSD and move it direct to the
> > HDD.
> >
> > Will it be good design to keep this algorithm open at block layer (as
> > proposed in patch.) ?
>
> It's almost always a good idea to avoid code duplication, but this patch
> definitely needs some work.

Jeff, I was not aware of the actual block layer module, so created just a
working patch to explain my point.
Check new patch. This patch is driver changes only in 
driver.

1. Below MR driver patch does similar things but code is Array base linear
lookup.
 http://marc.info/?l=linux-scsi=148245616108288=2

2. I thought to improve this using appended patch. It is similar of what
 is doing. This patch has duplicate code as  is doing the
same.

>
> I haven't looked terribly closely at the bcache implementaiton, so do
let me
> know if I've misinterpreted something.
>
> We should track streams per io_context/queue pair.  We already have a
data
> structure for that, the io_cq.  Right now that structure is tailored for
use by the
> I/O schedulers, but I'm sure we could rework that.  That would also get
rid of the
> tremedous amount of bloat this patch adds to the request_queue.  It will
also
> allow us to remove the bcache-specific fields that were added to
task_struct.
> Overall, it should be a good simplification, unless I've completely
missed the
> point (which happens).

Your understanding of requirement is correct. What we need is tracker of
 in block layer and check the tracker for every request to know
if this is a random or sequential IO.  As you explained, there is a
similar logic in  ..I search the kernel code and figure out below
code section @ block/elevator.c

/*
 * See if our hash lookup can find a potential backmerge.
 */
__rq = elv_rqhash_find(q, bio->bi_iter.bi_sector);


I am looking for similar logic done in elv_rqhash_find() for all the IOs
and provide information in request, if this particular request is a
potential back-merge candidate (Having new req_flags_t e.a  RQF_SEQ) . It
is OK, even thought it was not merged due to other checks in IO path.

Safer side (to avoid any performance issues), we can opt for API to be
called by low level driver on particular request queue/sdev, if someone is
interested in this request queue such help ?

I need help (some level of patch to work on) or pointer, if this path is
good. I can drive this, but need to understand direction.

>
> I don't like that you put sequential I/O detection into bio_check_eod.
> Split it out into its own function.

Sorry for this. I thought of sending patch to get better understanding. My
first patch was very high level and not complaint with many design or
coding issue.
For my learning - BTW, for such post (if I have high level patch) ..what
shall I do ?

> You've added a member to struct bio that isn't referenced.  It would
have been
> nice of you to put enough work into this RFC so that we could at least
see how
> the common code was used by bcache and your driver.

See my second patch appended here. I can work on block layer generic
changes, if we have some another area (as mentioned elevator/cfq) doing
the stuffs which I am looking for.

>
> EWMA (exponentially weighted moving average) is not an acronym I keep
handy
> in my head.  It would be nice to add documentation on the algorithm and
design
> choices.  More comments in the code would also be appreciated.  CFQ does
> some similar things (detecting sequential vs. seeky I/O) in a much
lighter-weight
> fashion.  Any change to the algorithm, of course, would have to be
verified to
> still meet bcache's needs.
>
> A queue flag might be a better way for the driver to request this
functionality.
>
> Coding style will definitely need 

Re: [PATCH] preview - block layer help to detect sequential IO

[Jeff Moyer]

Hi, Kashyap,

I'm CC-ing Kent, seeing how this is his code.

Kashyap Desai  writes:

> Objective of this patch is - 
>
> To move code used in bcache module in block layer which is used to
> find IO stream.  Reference code @drivers/md/bcache/request.c
> check_should_bypass().  This is a high level patch for review and
> understand if it is worth to follow ?
>
> As of now bcache module use this logic, but good to have it in block
> layer and expose function for external use.
>
> In this patch, I move logic of sequential IO search in block layer and
> exposed function blk_queue_rq_seq_cutoff.  Low level driver just need
> to call if they want stream detection per request queue.  For my
> testing I just added call blk_queue_rq_seq_cutoff(sdev->request_queue,
> 4) megaraid_sas driver.
>  
> In general, code of bcache module was referred and they are doing
> almost same as what we want to do in megaraid_sas driver below patch -
>
> http://marc.info/?l=linux-scsi=148245616108288=2
>  
> bcache implementation use search algorithm (hashed based on bio start
> sector) and detects 128 streams.  wanted those implementation
> to skip sequential IO to be placed on SSD and move it direct to the
> HDD.
>
> Will it be good design to keep this algorithm open at block layer (as
> proposed in patch.) ?

It's almost always a good idea to avoid code duplication, but this patch
definitely needs some work.

I haven't looked terribly closely at the bcache implementaiton, so do
let me know if I've misinterpreted something.

We should track streams per io_context/queue pair.  We already have a
data structure for that, the io_cq.  Right now that structure is
tailored for use by the I/O schedulers, but I'm sure we could rework
that.  That would also get rid of the tremedous amount of bloat this
patch adds to the request_queue.  It will also allow us to remove the
bcache-specific fields that were added to task_struct.  Overall, it
should be a good simplification, unless I've completely missed the point
(which happens).

I don't like that you put sequential I/O detection into bio_check_eod.
Split it out into its own function.

You've added a member to struct bio that isn't referenced.  It would
have been nice of you to put enough work into this RFC so that we could
at least see how the common code was used by bcache and your driver.

EWMA (exponentially weighted moving average) is not an acronym I keep
handy in my head.  It would be nice to add documentation on the
algorithm and design choices.  More comments in the code would also be
appreciated.  CFQ does some similar things (detecting sequential
vs. seeky I/O) in a much lighter-weight fashion.  Any change to the
algorithm, of course, would have to be verified to still meet bcache's
needs.

A queue flag might be a better way for the driver to request this
functionality.

Coding style will definitely need fixing.

I hope that was helpful.

Cheers,
Jeff

>
> Signed-off-by: Kashyap desai 
> ---
> diff --git a/block/blk-core.c b/block/blk-core.c
> index 14d7c07..2e93d14 100644
> --- a/block/blk-core.c
> +++ b/block/blk-core.c
> @@ -693,6 +693,7 @@ struct request_queue *blk_alloc_queue_node(gfp_t 
> gfp_mask, int node_id)
>  {
>   struct request_queue *q;
>   int err;
> + struct seq_io_tracker *io;
>  
>   q = kmem_cache_alloc_node(blk_requestq_cachep,
>   gfp_mask | __GFP_ZERO, node_id);
> @@ -761,6 +762,15 @@ struct request_queue *blk_alloc_queue_node(gfp_t 
> gfp_mask, int node_id)
>  
>   if (blkcg_init_queue(q))
>   goto fail_ref;
> + 
> + q->sequential_cutoff = 0;
> + spin_lock_init(>io_lock);
> + INIT_LIST_HEAD(>io_lru);
> +
> + for (io = q->io; io < q->io + BLK_RECENT_IO; io++) {
> + list_add(>lru, >io_lru);
> + hlist_add_head(>hash, q->io_hash + BLK_RECENT_IO);
> + }
>  
>   return q;
>  
> @@ -1876,6 +1886,26 @@ static inline int bio_check_eod(struct bio *bio, 
> unsigned int nr_sectors)
>   return 0;
>  }
>  
> +static void add_sequential(struct task_struct *t)
> +{
> +#define blk_ewma_add(ewma, val, weight, factor) \
> +({  \
> +(ewma) *= (weight) - 1; \
> +(ewma) += (val) << factor;  \
> +(ewma) /= (weight); \
> +(ewma) >> factor;   \
> +})
> +
> + blk_ewma_add(t->sequential_io_avg,
> +  t->sequential_io, 8, 0);
> +
> + t->sequential_io = 0;
> +}
> +static struct hlist_head *blk_iohash(struct request_queue *q, uint64_t k)
> +{
> + return >io_hash[hash_64(k, BLK_RECENT_IO_BITS)];
> +}
> +
>  static noinline_for_stack bool
>  generic_make_request_checks(struct bio *bio)
>  {
> @@ -1884,6 +1914,7 @@ 

RE: [PATCH] preview - block layer help to detect sequential IO

[Kashyap Desai]

> -Original Message-
> From: kbuild test robot [mailto:l...@intel.com]
> Sent: Thursday, January 12, 2017 1:18 AM
> To: Kashyap Desai
> Cc: kbuild-...@01.org; linux-scsi@vger.kernel.org;
linux-bl...@vger.kernel.org;
> ax...@kernel.dk; martin.peter...@oracle.com; j...@linux.vnet.ibm.com;
> sumit.sax...@broadcom.com; Kashyap desai
> Subject: Re: [PATCH] preview - block layer help to detect sequential IO
>
> Hi Kashyap,
>
> [auto build test ERROR on v4.9-rc8]
> [cannot apply to block/for-next linus/master linux/master next-20170111]
[if
> your patch is applied to the wrong git tree, please drop us a note to
help
> improve the system]
>
> url:
https://github.com/0day-ci/linux/commits/Kashyap-Desai/preview-block-
> layer-help-to-detect-sequential-IO/20170112-024228
> config: i386-randconfig-a0-201702 (attached as .config)
> compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
> reproduce:
> # save the attached .config to linux build tree
> make ARCH=i386
>
> All errors (new ones prefixed by >>):
>
>block/blk-core.c: In function 'add_sequential':
> >> block/blk-core.c:1899:16: error: 'struct task_struct' has no member
named
> 'sequential_io_avg'
>  blk_ewma_add(t->sequential_io_avg,


This error fixable. For now, I just wanted to get high level review of the
idea.
Below defines are required to use sequential_io and sequential_io_avg. I
have enable BCACHE for my testing in .config.

#if defined(CONFIG_BCACHE) || defined(CONFIG_BCACHE_MODULE)
unsigned intsequential_io;
unsigned intsequential_io_avg;
#endif

Looking for high level review comment.

` Kashyap


>^
>block/blk-core.c:1893:10: note: in definition of macro 'blk_ewma_add'
> (ewma) *= (weight) - 1;
\
>  ^~~~
> >> block/blk-core.c:1899:16: error: 'struct task_struct' has no member
named
> 'sequential_io_avg'
>  blk_ewma_add(t->sequential_io_avg,
>^
>block/blk-core.c:1894:10: note: in definition of macro 'blk_ewma_add'
> (ewma) += (val) << factor;
\
>  ^~~~
> >> block/blk-core.c:1900:5: error: 'struct task_struct' has no member
named
> 'sequential_io'
>t->sequential_io, 8, 0);
> ^
>block/blk-core.c:1894:20: note: in definition of macro 'blk_ewma_add'
> (ewma) += (val) << factor;
\
>^~~
> >> block/blk-core.c:1899:16: error: 'struct task_struct' has no member
named
> 'sequential_io_avg'
>  blk_ewma_add(t->sequential_io_avg,
>^
>block/blk-core.c:1895:10: note: in definition of macro 'blk_ewma_add'
> (ewma) /= (weight);
\
>  ^~~~
> >> block/blk-core.c:1899:16: error: 'struct task_struct' has no member
named
> 'sequential_io_avg'
>  blk_ewma_add(t->sequential_io_avg,
>^
>block/blk-core.c:1896:10: note: in definition of macro 'blk_ewma_add'
> (ewma) >> factor;
\
>  ^~~~
>block/blk-core.c:1902:3: error: 'struct task_struct' has no member
named
> 'sequential_io'
>  t->sequential_io = 0;
>   ^~
>block/blk-core.c: In function 'generic_make_request_checks':
>block/blk-core.c:2012:7: error: 'struct task_struct' has no member
named
> 'sequential_io'
>   task->sequential_io  = i->sequential;
>   ^~
>In file included from block/blk-core.c:14:0:
>block/blk-core.c:2020:21: error: 'struct task_struct' has no member
named
> 'sequential_io'
>   sectors = max(task->sequential_io,
> ^
>include/linux/kernel.h:747:2: note: in definition of macro '__max'
>  t1 max1 = (x); \
>  ^~
>block/blk-core.c:2020:13: note: in expansion of macro 'max'
>   sectors = max(task->sequential_io,
> ^~~
>block/blk-core.c:2020:21: error: 'struct task_struct' has no member
named
> 'sequential_io'
>   sectors = max(task->sequential_io,
> ^
>include/linux/kernel.h:747:13: note: in definition of macro '__max'
>  t1 max1 = (x); \
> ^
>block/blk-core.c:2020:13: note: in expansion of macro 'max'
>   sectors = max(task->sequential_io,
> ^~~
>block/blk-core.c:2021:14: error: 'struct task_struct' has no member
named
> 'sequential_io_avg'
>  task->sequential_io_avg) >> 9;
>  ^
>include/linux/kernel.h:748:2: note: in definition of macro '__max'
>  t2 max2 = (y); \
>  ^~
>block/blk-core.c:2020:13: note: in expansion of macro 'max'
>   sectors = max(task->sequential_i

Re: [PATCH] preview - block layer help to detect sequential IO

[kbuild test robot]

Hi Kashyap,

[auto build test ERROR on v4.9-rc8]
[cannot apply to block/for-next linus/master linux/master next-20170111]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Kashyap-Desai/preview-block-layer-help-to-detect-sequential-IO/20170112-024228
config: i386-randconfig-a0-201702 (attached as .config)
compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
reproduce:
# save the attached .config to linux build tree
make ARCH=i386 

All errors (new ones prefixed by >>):

   block/blk-core.c: In function 'add_sequential':
>> block/blk-core.c:1899:16: error: 'struct task_struct' has no member named 
>> 'sequential_io_avg'
 blk_ewma_add(t->sequential_io_avg,
   ^
   block/blk-core.c:1893:10: note: in definition of macro 'blk_ewma_add'
(ewma) *= (weight) - 1; \
 ^~~~
>> block/blk-core.c:1899:16: error: 'struct task_struct' has no member named 
>> 'sequential_io_avg'
 blk_ewma_add(t->sequential_io_avg,
   ^
   block/blk-core.c:1894:10: note: in definition of macro 'blk_ewma_add'
(ewma) += (val) << factor;  \
 ^~~~
>> block/blk-core.c:1900:5: error: 'struct task_struct' has no member named 
>> 'sequential_io'
   t->sequential_io, 8, 0);
^
   block/blk-core.c:1894:20: note: in definition of macro 'blk_ewma_add'
(ewma) += (val) << factor;  \
   ^~~
>> block/blk-core.c:1899:16: error: 'struct task_struct' has no member named 
>> 'sequential_io_avg'
 blk_ewma_add(t->sequential_io_avg,
   ^
   block/blk-core.c:1895:10: note: in definition of macro 'blk_ewma_add'
(ewma) /= (weight); \
 ^~~~
>> block/blk-core.c:1899:16: error: 'struct task_struct' has no member named 
>> 'sequential_io_avg'
 blk_ewma_add(t->sequential_io_avg,
   ^
   block/blk-core.c:1896:10: note: in definition of macro 'blk_ewma_add'
(ewma) >> factor;   \
 ^~~~
   block/blk-core.c:1902:3: error: 'struct task_struct' has no member named 
'sequential_io'
 t->sequential_io = 0;
  ^~
   block/blk-core.c: In function 'generic_make_request_checks':
   block/blk-core.c:2012:7: error: 'struct task_struct' has no member named 
'sequential_io'
  task->sequential_io  = i->sequential;
  ^~
   In file included from block/blk-core.c:14:0:
   block/blk-core.c:2020:21: error: 'struct task_struct' has no member named 
'sequential_io'
  sectors = max(task->sequential_io,
^
   include/linux/kernel.h:747:2: note: in definition of macro '__max'
 t1 max1 = (x); \
 ^~
   block/blk-core.c:2020:13: note: in expansion of macro 'max'
  sectors = max(task->sequential_io,
^~~
   block/blk-core.c:2020:21: error: 'struct task_struct' has no member named 
'sequential_io'
  sectors = max(task->sequential_io,
^
   include/linux/kernel.h:747:13: note: in definition of macro '__max'
 t1 max1 = (x); \
^
   block/blk-core.c:2020:13: note: in expansion of macro 'max'
  sectors = max(task->sequential_io,
^~~
   block/blk-core.c:2021:14: error: 'struct task_struct' has no member named 
'sequential_io_avg'
 task->sequential_io_avg) >> 9;
 ^
   include/linux/kernel.h:748:2: note: in definition of macro '__max'
 t2 max2 = (y); \
 ^~
   block/blk-core.c:2020:13: note: in expansion of macro 'max'
  sectors = max(task->sequential_io,
^~~
   block/blk-core.c:2021:14: error: 'struct task_struct' has no member named 
'sequential_io_avg'
 task->sequential_io_avg) >> 9;
 ^
   include/linux/kernel.h:748:13: note: in definition of macro '__max'
 t2 max2 = (y); \
^
   block/blk-core.c:2020:13: note: in expansion of macro 'max'
  sectors = max(task->sequential_io,
^~~

vim +1899 block/blk-core.c

  1887  }
  1888  
  1889  static void add_sequential(struct task_struct *t)
  1890  {
  1891  #define blk_ewma_add(ewma, val, weight, factor) 
\
  1892  ({  
\
> 1893  (ewma) *= (weight) - 1; 
> \
  1894  (ewma) += (val) << factor;  
\
  1895  (ewma) /= (weight); 
\
  1896  (ewma) >> factor;   
\
  1897  })
  1898  
> 1899  blk_ewma_add(t->sequential_io_avg,
> 1900   t->sequential_io, 8, 0);
  1901  
  

[PATCH] preview - block layer help to detect sequential IO

[Kashyap Desai]

Objective of this patch is - 

To move code used in bcache module in block layer which is used to find IO 
stream. 
Reference code @drivers/md/bcache/request.c check_should_bypass().
This is a high level patch for review and understand if it is worth to follow ?

As of now bcache module use this logic, but good to have it in block layer and 
expose function for external use.

In this patch, I move logic of sequential IO search in block layer and exposed 
function blk_queue_rq_seq_cutoff.
Low level driver just need to call if they want stream detection per request 
queue. 
For my testing I just added call blk_queue_rq_seq_cutoff(sdev->request_queue, 
4) megaraid_sas driver.
 
In general, code of bcache module was referred and they are doing almost same 
as what we want to do in 
megaraid_sas driver below patch -

http://marc.info/?l=linux-scsi=148245616108288=2
 
bcache implementation use search algorithm (hashed based on bio start sector)
and detects 128 streams.  wanted those implementation to skip 
sequential IO 
to be placed on SSD and move it direct to the HDD. 

Will it be good design to keep this algorithm open at block layer (as proposed 
in patch.) ?

Signed-off-by: Kashyap desai 
---
diff --git a/block/blk-core.c b/block/blk-core.c
index 14d7c07..2e93d14 100644
--- a/block/blk-core.c
+++ b/block/blk-core.c
@@ -693,6 +693,7 @@ struct request_queue *blk_alloc_queue_node(gfp_t gfp_mask, 
int node_id)
 {
struct request_queue *q;
int err;
+   struct seq_io_tracker *io;
 
q = kmem_cache_alloc_node(blk_requestq_cachep,
gfp_mask | __GFP_ZERO, node_id);
@@ -761,6 +762,15 @@ struct request_queue *blk_alloc_queue_node(gfp_t gfp_mask, 
int node_id)
 
if (blkcg_init_queue(q))
goto fail_ref;
+   
+   q->sequential_cutoff = 0;
+   spin_lock_init(>io_lock);
+   INIT_LIST_HEAD(>io_lru);
+
+   for (io = q->io; io < q->io + BLK_RECENT_IO; io++) {
+   list_add(>lru, >io_lru);
+   hlist_add_head(>hash, q->io_hash + BLK_RECENT_IO);
+   }
 
return q;
 
@@ -1876,6 +1886,26 @@ static inline int bio_check_eod(struct bio *bio, 
unsigned int nr_sectors)
return 0;
 }
 
+static void add_sequential(struct task_struct *t)
+{
+#define blk_ewma_add(ewma, val, weight, factor) \
+({  \
+(ewma) *= (weight) - 1; \
+(ewma) += (val) << factor;  \
+(ewma) /= (weight); \
+(ewma) >> factor;   \
+})
+
+   blk_ewma_add(t->sequential_io_avg,
+t->sequential_io, 8, 0);
+
+   t->sequential_io = 0;
+}
+static struct hlist_head *blk_iohash(struct request_queue *q, uint64_t k)
+{
+   return >io_hash[hash_64(k, BLK_RECENT_IO_BITS)];
+}
+
 static noinline_for_stack bool
 generic_make_request_checks(struct bio *bio)
 {
@@ -1884,6 +1914,7 @@ static inline int bio_check_eod(struct bio *bio, unsigned 
int nr_sectors)
int err = -EIO;
char b[BDEVNAME_SIZE];
struct hd_struct *part;
+   struct task_struct *task = current;
 
might_sleep();
 
@@ -1957,6 +1988,42 @@ static inline int bio_check_eod(struct bio *bio, 
unsigned int nr_sectors)
if (!blkcg_bio_issue_check(q, bio))
return false;
 
+   if (q->sequential_cutoff) {
+   struct seq_io_tracker *i;
+   unsigned sectors;
+
+   spin_lock(>io_lock);
+
+   hlist_for_each_entry(i, blk_iohash(q, bio->bi_iter.bi_sector), 
hash)
+   if (i->last == bio->bi_iter.bi_sector &&
+   time_before(jiffies, i->jiffies))
+   goto found;
+
+   i = list_first_entry(>io_lru, struct seq_io_tracker, lru);
+
+   add_sequential(task);
+   i->sequential = 0;
+found:
+   if (i->sequential + bio->bi_iter.bi_size > i->sequential)
+   i->sequential   += bio->bi_iter.bi_size;
+
+   i->last  = bio_end_sector(bio);
+   i->jiffies   = jiffies + msecs_to_jiffies(5000);
+   task->sequential_io  = i->sequential;
+
+   hlist_del(>hash);
+   hlist_add_head(>hash, blk_iohash(q, i->last));
+   list_move_tail(>lru, >io_lru);
+
+   spin_unlock(>io_lock);
+
+   sectors = max(task->sequential_io,
+ task->sequential_io_avg) >> 9;
+   if (sectors >= q->sequential_cutoff >> 9) {
+   bio->is_sequential = true;
+   }
+   }
+
trace_block_bio_queue(q, bio);
return true;
 
diff --git a/block/blk-mq.c