Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1592554 > unrolled thread

[PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq

Back to article view | Back to linux.kernel

Contents

  [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Paolo Valente <paolo.valente@linaro.org> - 2017-03-04 17:10 +0100
    Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler  as an extra scheduler Jens Axboe <axboe@kernel.dk> - 2017-03-05 16:30 +0100
      Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-03-05 17:10 +0100
        Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler  as an extra scheduler Jens Axboe <axboe@kernel.dk> - 2017-03-06 23:30 +0100
          Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-03-14 12:30 +0100
    Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Markus Trippelsdorf <markus@trippelsdorf.de> - 2017-03-06 08:50 +0100
    Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Jens Axboe <axboe@kernel.dk> - 2017-03-07 20:40 +0100
      Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Paolo Valente <paolo.valente@linaro.org> - 2017-03-15 13:10 +0100
        Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Jens Axboe <axboe@kernel.dk> - 2017-03-15 17:00 +0100
          Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Jens Axboe <axboe@kernel.dk> - 2017-03-15 17:40 +0100
            Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Paolo Valente <paolo.valente@linaro.org> - 2017-03-15 18:10 +0100
              Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Jens Axboe <axboe@kernel.dk> - 2017-03-15 22:10 +0100
                Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Paolo Valente <paolo.valente@linaro.org> - 2017-03-18 11:40 +0100
    Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler  as an extra scheduler Jens Axboe <axboe@kernel.dk> - 2017-03-08 00:30 +0100
      Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-03-18 13:50 +0100
    Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-03-14 15:20 +0100
    Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Paolo Valente <paolo.valente@linaro.org> - 2017-03-14 15:20 +0100
    Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Paolo Valente <paolo.valente@linaro.org> - 2017-03-14 16:40 +0100
      Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Jens Axboe <axboe@kernel.dk> - 2017-03-14 16:50 +0100
      Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Paolo Valente <paolo.valente@linaro.org> - 2017-03-18 12:00 +0100
        Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Linus Walleij <linus.walleij@linaro.org> - 2017-03-18 18:20 +0100
          Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Linus Walleij <linus.walleij@linaro.org> - 2017-03-18 21:50 +0100
          Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Paolo Valente <paolo.valente@linaro.org> - 2017-03-19 13:20 +0100
          Re: [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq Jens Axboe <axboe@kernel.dk> - 2017-03-20 19:50 +0100
    Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Jens Axboe <axboe@kernel.dk> - 2017-03-15 18:00 +0100
      Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Paolo Valente <paolo.valente@linaro.org> - 2017-03-15 18:10 +0100
        Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM) Jens Axboe <axboe@kernel.dk> - 2017-03-15 22:10 +0100
    Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-03-18 13:20 +0100
      Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-03-19 13:00 +0100

Page 1 of 2  [1] 2  Next page →

#1592554 — [PATCH RFC 00/14] Add the BFQ I/O Scheduler to blk-mq

Hi,
at last, here is my first patch series meant for merging. It adds BFQ
to blk-mq. Don't worry, in this message I won't bore you again with
the wonderful properties of BFQ :)

A quick update on the status of the code: thanks to Murphy's laws, in
the last handful of days,
1) A kind of rare failure, reported only once by a user, several
months ago, has been reported again. Fortunately, the bug reporter
provided an oops this time.
2) An unexpected bandwidth unbalance between greedy reads and writes
has been noted.
I have chosen however to submit these patches before attacking these
new problems.

Let me also recall the limitations of the current version of BFQ. On
average CPUs, it can handle, without loss of throughput or fairness
guarantees, devices performing at most ~30K IOPS; at most ~50 KIOPS on
faster CPUs. Just to put this into context, these are about the same
limits as CFQ in blk. A second intrinsic problem is the current need
for device idling when differentiated bandwidth distribution must be
guaranteed.  Over the last months, I have seen that, fortunately,
there is room for significant improvements with both these
limitations. I plan to work on these improvements after we are done
(and if everything goes well) with merging BFQ.

Finally, a few details on the patchset.

The first two patches introduce BFQ-v0, which is more or less the
first version of BFQ submitted a few years ago [1].  The remaining
patches turn progressively BFQ-v0 into BFQ-v8r8, the current version
of BFQ.

Some patch generates WARNINGS with checkpatch.pl, but these WARNINGS
seem to be either unavoidable for the involved pieces of code (which
the patch just extends), or false positives.

Thanks,
Paolo

[1] https://lkml.org/lkml/2008/4/1/234

Arianna Avanzini (4):
  block, bfq: add full hierarchical scheduling and cgroups support
  block, bfq: add Early Queue Merge (EQM)
  block, bfq: reduce idling only in symmetric scenarios
  block, bfq: handle bursts of queue activations

Paolo Valente (10):
  block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler
  block, bfq: improve throughput boosting
  block, bfq: modify the peak-rate estimator
  block, bfq: add more fairness with writes and slow processes
  block, bfq: improve responsiveness
  block, bfq: reduce I/O latency for soft real-time applications
  block, bfq: preserve a low latency also with NCQ-capable drives
  block, bfq: reduce latency during request-pool saturation
  block, bfq: boost the throughput on NCQ-capable flash-based devices
  block, bfq: boost the throughput with random I/O on NCQ-capable HDDs

 Documentation/block/00-INDEX        |    2 +
 Documentation/block/bfq-iosched.txt |  530 +++
 block/Kconfig.iosched               |   21 +
 block/Makefile                      |    1 +
 block/bfq-iosched.c                 | 8751 +++++++++++++++++++++++++++++++++++
 block/elevator.c                    |   16 +-
 include/linux/blkdev.h              |    2 +-
 7 files changed, 9317 insertions(+), 6 deletions(-)
 create mode 100644 Documentation/block/bfq-iosched.txt
 create mode 100644 block/bfq-iosched.c

--
2.10.0

[toc] | [next] | [standalone]

#1592781 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

On 03/04/2017 09:01 AM, Paolo Valente wrote:
> We tag as v0 the version of BFQ containing only BFQ's engine plus
> hierarchical support. BFQ's engine is introduced by this commit, while
> hierarchical support is added by next commit. We use the v0 tag to
> distinguish this minimal version of BFQ from the versions containing
> also the features and the improvements added by next commits. BFQ-v0
> coincides with the version of BFQ submitted a few years ago [1], apart
> from the introduction of preemption, described below.
> 
> BFQ is a proportional-share I/O scheduler, whose general structure,
> plus a lot of code, are borrowed from CFQ.

I'll take a closer look at this in the coming week. But one quick
comment - don't default to BFQ. Both because it might not be fully
stable yet, and also because the performance limitation of it is
quite severe. Whereas deadline doesn't really hurt single queue
flash at all, BFQ will.

Generally, I think that sort of logic should go into a udev rule. If
a device is rotational it should default to BFQ once the dust has
settled.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1592786 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

> Il giorno 05 mar 2017, alle ore 16:16, Jens Axboe <axboe@kernel.dk> ha scritto:
> 
> On 03/04/2017 09:01 AM, Paolo Valente wrote:
>> We tag as v0 the version of BFQ containing only BFQ's engine plus
>> hierarchical support. BFQ's engine is introduced by this commit, while
>> hierarchical support is added by next commit. We use the v0 tag to
>> distinguish this minimal version of BFQ from the versions containing
>> also the features and the improvements added by next commits. BFQ-v0
>> coincides with the version of BFQ submitted a few years ago [1], apart
>> from the introduction of preemption, described below.
>> 
>> BFQ is a proportional-share I/O scheduler, whose general structure,
>> plus a lot of code, are borrowed from CFQ.
> 
> I'll take a closer look at this in the coming week.

ok

> But one quick
> comment - don't default to BFQ. Both because it might not be fully
> stable yet, and also because the performance limitation of it is
> quite severe. Whereas deadline doesn't really hurt single queue
> flash at all, BFQ will.
> 

Ok, sorry.  I was doubtful on what to do, but, to not bother you on
every details, I went for setting it as default, because I thought
people would have preferred to test it, even from boot, in this
preliminary stage.  I reset elevator.c in the submission, unless you
want me to do it even before receiving your and others' reviews.

> Generally, I think that sort of logic should go into a udev rule. If
> a device is rotational it should default to BFQ once the dust has
> settled.
> 

ok

Looking forward for your feedback,
Paolo

> -- 
> Jens Axboe
> 

[toc] | [prev] | [next] | [standalone]

#1593771 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

On 03/05/2017 09:02 AM, Paolo Valente wrote:
> 
>> Il giorno 05 mar 2017, alle ore 16:16, Jens Axboe <axboe@kernel.dk> ha scritto:
>>
>> On 03/04/2017 09:01 AM, Paolo Valente wrote:
>>> We tag as v0 the version of BFQ containing only BFQ's engine plus
>>> hierarchical support. BFQ's engine is introduced by this commit, while
>>> hierarchical support is added by next commit. We use the v0 tag to
>>> distinguish this minimal version of BFQ from the versions containing
>>> also the features and the improvements added by next commits. BFQ-v0
>>> coincides with the version of BFQ submitted a few years ago [1], apart
>>> from the introduction of preemption, described below.
>>>
>>> BFQ is a proportional-share I/O scheduler, whose general structure,
>>> plus a lot of code, are borrowed from CFQ.
>>
>> I'll take a closer look at this in the coming week.
> 
> ok
> 
>> But one quick
>> comment - don't default to BFQ. Both because it might not be fully
>> stable yet, and also because the performance limitation of it is
>> quite severe. Whereas deadline doesn't really hurt single queue
>> flash at all, BFQ will.
>>
> 
> Ok, sorry.  I was doubtful on what to do, but, to not bother you on
> every details, I went for setting it as default, because I thought
> people would have preferred to test it, even from boot, in this
> preliminary stage.  I reset elevator.c in the submission, unless you
> want me to do it even before receiving your and others' reviews.

I don't think it's stable enough for that yet, it's seen very little
testing outside of your own testing. Given that, it's much better that
people opt in to testing BFQ, so they at least know they can expect
crashes.

Speaking of testing, I ran into this bug:

[ 9469.621413] general protection fault: 0000 [#1] PREEMPT SMP
[ 9469.627872] Modules linked in: loop dm_mod xfs libcrc32c bfq_iosched x86_pkg_temp_thermal btrfe
[ 9469.648196] CPU: 0 PID: 2114 Comm: kworker/0:1H Tainted: G        W       4.11.0-rc1+ #249
[ 9469.657873] Hardware name: Dell Inc. PowerEdge T630/0NT78X, BIOS 2.3.4 11/09/2016
[ 9469.666742] Workqueue: xfs-log/nvme4n1p1 xfs_buf_ioend_work [xfs]
[ 9469.674213] task: ffff881fe97646c0 task.stack: ffff881ff13d0000
[ 9469.681053] RIP: 0010:__bfq_bfqq_expire+0xb3/0x110 [bfq_iosched]
[ 9469.687991] RSP: 0018:ffff881fff603dd8 EFLAGS: 00010082
[ 9469.694052] RAX: 6b6b6b6b6b6b6b6b RBX: ffff883fe8e0eb58 RCX: 0000000000010004
[ 9469.702251] RDX: 0000000000010004 RSI: 0000000000000000 RDI: 00000000ffffffff
[ 9469.710456] RBP: ffff881fff603de8 R08: 0000000000000000 R09: 0000000000000001
[ 9469.718659] R10: 0000000000000001 R11: 0000000000000000 R12: ffff883fe8dbf4e8
[ 9469.726863] R13: 0000000000000000 R14: 0000000000000001 R15: 0000000000007904
[ 9469.735063] FS:  0000000000000000(0000) GS:ffff881fff600000(0000) knlGS:0000000000000000
[ 9469.744539] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 9469.751189] CR2: 00000000020c0018 CR3: 0000001fec1db000 CR4: 00000000003406f0
[ 9469.759392] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[ 9469.767596] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
[ 9469.775794] Call Trace:
[ 9469.778748]  <IRQ>
[ 9469.781222]  bfq_bfqq_expire+0x104/0x2f0 [bfq_iosched]
[ 9469.787193]  ? bfq_idle_slice_timer+0x2a/0xc0 [bfq_iosched]
[ 9469.793650]  bfq_idle_slice_timer+0x7c/0xc0 [bfq_iosched]
[ 9469.799914]  __hrtimer_run_queues+0xd9/0x500
[ 9469.804911]  ? bfq_rq_enqueued+0x340/0x340 [bfq_iosched]
[ 9469.811072]  hrtimer_interrupt+0xb0/0x200
[ 9469.815781]  local_apic_timer_interrupt+0x31/0x50
[ 9469.821264]  smp_apic_timer_interrupt+0x33/0x50
[ 9469.826555]  apic_timer_interrupt+0x90/0xa0

just running the xfstest suite. It's test generic/299. Have you done
full runs of xfstest? I'd greatly recommend that for shaking out bugs.
Run a full loop with xfs, one with btrfs, and one with ext4 for better
confidence in the stability of the code.

(gdb) l *__bfq_bfqq_expire+0xb3
0x5983 is in __bfq_bfqq_expire (block/bfq-iosched.c:2664).
2659		 * been properly deactivated or requeued, so we can safely
2660		 * execute the final step: reset in_service_entity along the
2661		 * path from entity to the root.
2662		 */
2663		for_each_entity(entity)
2664			entity->sched_data->in_service_entity = NULL;
2665	}
2666	
2667	static void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2668					bool ins_into_idle_tree, bool expiration)

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1600240 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

> Il giorno 06 mar 2017, alle ore 21:46, Jens Axboe <axboe@kernel.dk> ha scritto:
> 
> On 03/05/2017 09:02 AM, Paolo Valente wrote:
>> 
>>> Il giorno 05 mar 2017, alle ore 16:16, Jens Axboe <axboe@kernel.dk> ha scritto:
>>> 
>>> On 03/04/2017 09:01 AM, Paolo Valente wrote:
>>>> We tag as v0 the version of BFQ containing only BFQ's engine plus
>>>> hierarchical support. BFQ's engine is introduced by this commit, while
>>>> hierarchical support is added by next commit. We use the v0 tag to
>>>> distinguish this minimal version of BFQ from the versions containing
>>>> also the features and the improvements added by next commits. BFQ-v0
>>>> coincides with the version of BFQ submitted a few years ago [1], apart
>>>> from the introduction of preemption, described below.
>>>> 
>>>> BFQ is a proportional-share I/O scheduler, whose general structure,
>>>> plus a lot of code, are borrowed from CFQ.
>>> 
>>> I'll take a closer look at this in the coming week.
>> 
>> ok
>> 
>>> But one quick
>>> comment - don't default to BFQ. Both because it might not be fully
>>> stable yet, and also because the performance limitation of it is
>>> quite severe. Whereas deadline doesn't really hurt single queue
>>> flash at all, BFQ will.
>>> 
>> 
>> Ok, sorry.  I was doubtful on what to do, but, to not bother you on
>> every details, I went for setting it as default, because I thought
>> people would have preferred to test it, even from boot, in this
>> preliminary stage.  I reset elevator.c in the submission, unless you
>> want me to do it even before receiving your and others' reviews.
> 
> I don't think it's stable enough for that yet, it's seen very little
> testing outside of your own testing.

Hi Jens.

Yes, sorry, in general people of course use a kernel for a little bit
more than just testing bfq ...

> Given that, it's much better that
> people opt in to testing BFQ, so they at least know they can expect
> crashes.
> 
> Speaking of testing, I ran into this bug:
> 
> [ 9469.621413] general protection fault: 0000 [#1] PREEMPT SMP
> [ 9469.627872] Modules linked in: loop dm_mod xfs libcrc32c bfq_iosched x86_pkg_temp_thermal btrfe
> [ 9469.648196] CPU: 0 PID: 2114 Comm: kworker/0:1H Tainted: G        W       4.11.0-rc1+ #249
> [ 9469.657873] Hardware name: Dell Inc. PowerEdge T630/0NT78X, BIOS 2.3.4 11/09/2016
> [ 9469.666742] Workqueue: xfs-log/nvme4n1p1 xfs_buf_ioend_work [xfs]
> [ 9469.674213] task: ffff881fe97646c0 task.stack: ffff881ff13d0000
> [ 9469.681053] RIP: 0010:__bfq_bfqq_expire+0xb3/0x110 [bfq_iosched]
> [ 9469.687991] RSP: 0018:ffff881fff603dd8 EFLAGS: 00010082
> [ 9469.694052] RAX: 6b6b6b6b6b6b6b6b RBX: ffff883fe8e0eb58 RCX: 0000000000010004
> [ 9469.702251] RDX: 0000000000010004 RSI: 0000000000000000 RDI: 00000000ffffffff
> [ 9469.710456] RBP: ffff881fff603de8 R08: 0000000000000000 R09: 0000000000000001
> [ 9469.718659] R10: 0000000000000001 R11: 0000000000000000 R12: ffff883fe8dbf4e8
> [ 9469.726863] R13: 0000000000000000 R14: 0000000000000001 R15: 0000000000007904
> [ 9469.735063] FS:  0000000000000000(0000) GS:ffff881fff600000(0000) knlGS:0000000000000000
> [ 9469.744539] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> [ 9469.751189] CR2: 00000000020c0018 CR3: 0000001fec1db000 CR4: 00000000003406f0
> [ 9469.759392] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
> [ 9469.767596] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
> [ 9469.775794] Call Trace:
> [ 9469.778748]  <IRQ>
> [ 9469.781222]  bfq_bfqq_expire+0x104/0x2f0 [bfq_iosched]
> [ 9469.787193]  ? bfq_idle_slice_timer+0x2a/0xc0 [bfq_iosched]
> [ 9469.793650]  bfq_idle_slice_timer+0x7c/0xc0 [bfq_iosched]
> [ 9469.799914]  __hrtimer_run_queues+0xd9/0x500
> [ 9469.804911]  ? bfq_rq_enqueued+0x340/0x340 [bfq_iosched]
> [ 9469.811072]  hrtimer_interrupt+0xb0/0x200
> [ 9469.815781]  local_apic_timer_interrupt+0x31/0x50
> [ 9469.821264]  smp_apic_timer_interrupt+0x33/0x50
> [ 9469.826555]  apic_timer_interrupt+0x90/0xa0
> 
> just running the xfstest suite. It's test generic/299. Have you done
> full runs of xfstest? I'd greatly recommend that for shaking out bugs.
> Run a full loop with xfs, one with btrfs, and one with ext4 for better
> confidence in the stability of the code.
> 

Thanks for this information and suggestions.  I'm running xfstests
right now, to reproduce at least the failure you spotted.

Thanks,
Paolo

> (gdb) l *__bfq_bfqq_expire+0xb3
> 0x5983 is in __bfq_bfqq_expire (block/bfq-iosched.c:2664).
> 2659		 * been properly deactivated or requeued, so we can safely
> 2660		 * execute the final step: reset in_service_entity along the
> 2661		 * path from entity to the root.
> 2662		 */
> 2663		for_each_entity(entity)
> 2664			entity->sched_data->in_service_entity = NULL;
> 2665	}
> 2666	
> 2667	static void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
> 2668					bo

[toc] | [prev] | [next] | [standalone]

#1592975

On 2017.03.04 at 17:01 +0100, Paolo Valente wrote:
> Hi,
> at last, here is my first patch series meant for merging. It adds BFQ
> to blk-mq. Don't worry, in this message I won't bore you again with
> the wonderful properties of BFQ :)

I gave BFQ a quick try. Unfortunately it hangs when I try to delete
btrfs snapshots:

root       124  0.0  0.0      0     0 ?        D    07:19   0:03 [btrfs-cleaner]  
root       125  0.0  0.0      0     0 ?        D    07:19   0:00 [btrfs-transacti]

[ 4372.880116] sysrq: SysRq : Show Blocked State
[ 4372.880125]   task                        PC stack   pid father
[ 4372.880148] btrfs-cleaner   D    0   124      2 0x00000000
[ 4372.880156] Call Trace:
[ 4372.880166]  ? __schedule+0x160/0x7c0
[ 4372.880174]  ? io_schedule+0x64/0xe0
[ 4372.880179]  ? wait_on_page_bit+0x7a/0x100
[ 4372.880183]  ? devm_memunmap+0x40/0x40
[ 4372.880189]  ? read_extent_buffer_pages+0x25c/0x2c0
[ 4372.880195]  ? run_one_async_done+0xc0/0xc0
[ 4372.880200]  ? btree_read_extent_buffer_pages+0x60/0x2e0
[ 4372.880206]  ? read_tree_block+0x2c/0x60
[ 4372.880211]  ? read_block_for_search.isra.38+0xec/0x3a0
[ 4372.880217]  ? btrfs_search_slot+0x214/0xbc0
[ 4372.880221]  ? lookup_inline_extent_backref+0xfb/0x8c0
[ 4372.880225]  ? __btrfs_free_extent.isra.74+0xe9/0xdc0
[ 4372.880231]  ? btrfs_merge_delayed_refs+0x57/0x6e0
[ 4372.880235]  ? __btrfs_run_delayed_refs+0x60d/0x1340
[ 4372.880239]  ? btrfs_run_delayed_refs+0x64/0x280
[ 4372.880243]  ? btrfs_should_end_transaction+0x3b/0xa0
[ 4372.880247]  ? btrfs_drop_snapshot+0x3b2/0x800
[ 4372.880251]  ? __schedule+0x168/0x7c0
[ 4372.880254]  ? btrfs_clean_one_deleted_snapshot+0xa4/0xe0
[ 4372.880259]  ? cleaner_kthread+0x13a/0x180
[ 4372.880264]  ? btree_invalidatepage+0xc0/0xc0
[ 4372.880268]  ? kthread+0x144/0x180
[ 4372.880272]  ? kthread_flush_work_fn+0x20/0x20
[ 4372.880277]  ? ret_from_fork+0x23/0x30
[ 4372.880280] btrfs-transacti D    0   125      2 0x00000000
[ 4372.880285] Call Trace:
[ 4372.880290]  ? __schedule+0x160/0x7c0
[ 4372.880295]  ? io_schedule+0x64/0xe0
[ 4372.880300]  ? wait_on_page_bit_common.constprop.57+0x160/0x180
[ 4372.880303]  ? devm_memunmap+0x40/0x40
[ 4372.880307]  ? __filemap_fdatawait_range+0xd3/0x140
[ 4372.880311]  ? clear_state_bit.constprop.82+0xf7/0x180
[ 4372.880315]  ? __clear_extent_bit.constprop.79+0x138/0x3c0
[ 4372.880319]  ? filemap_fdatawait_range+0x9/0x60
[ 4372.880323]  ? __btrfs_wait_marked_extents.isra.18+0xc1/0x100
[ 4372.880327]  ? btrfs_write_and_wait_marked_extents.constprop.23+0x49/0x80
[ 4372.880331]  ? btrfs_commit_transaction+0x8e1/0xb00
[ 4372.880334]  ? join_transaction.constprop.24+0x10/0xa0
[ 4372.880340]  ? wake_bit_function+0x60/0x60
[ 4372.880345]  ? transaction_kthread+0x185/0x1a0
[ 4372.880350]  ? btrfs_cleanup_transaction+0x500/0x500
[ 4372.880354]  ? kthread+0x144/0x180
[ 4372.880358]  ? kthread_flush_work_fn+0x20/0x20
[ 4372.880362]  ? ret_from_fork+0x23/0x30
[ 4372.880367] ntpd            D    0   175      1 0x00000004
[ 4372.880372] Call Trace:
[ 4372.880375]  ? __schedule+0x160/0x7c0
[ 4372.880379]  ? schedule_preempt_disabled+0x2d/0x80
[ 4372.880383]  ? __mutex_lock.isra.5+0x17b/0x4c0
[ 4372.880386]  ? wait_current_trans+0x15/0xc0
[ 4372.880391]  ? btrfs_free_path+0xe/0x20
[ 4372.880395]  ? btrfs_pin_log_trans+0x14/0x40
[ 4372.880400]  ? btrfs_rename2+0x28e/0x19c0
[ 4372.880404]  ? path_init+0x187/0x3e0
[ 4372.880407]  ? unlazy_walk+0x4b/0x100
[ 4372.880410]  ? terminate_walk+0x8d/0x100
[ 4372.880414]  ? filename_parentat+0x1e9/0x2c0
[ 4372.880420]  ? __kmalloc_track_caller+0xc4/0x100
[ 4372.880424]  ? vfs_rename+0x33f/0x7e0
[ 4372.880428]  ? SYSC_renameat2+0x53c/0x680
[ 4372.880433]  ? entry_SYSCALL_64_fastpath+0x13/0x94
[ 4372.880437] fcron           D    0   178      1 0x00000000
[ 4372.880441] Call Trace:
[ 4372.880445]  ? __schedule+0x160/0x7c0
[ 4372.880448]  ? schedule_preempt_disabled+0x2d/0x80
[ 4372.880452]  ? __mutex_lock.isra.5+0x17b/0x4c0
[ 4372.880458]  ? pagevec_lookup_tag+0x18/0x20
[ 4372.880462]  ? btrfs_log_dentry_safe+0x4cd/0xac0
[ 4372.880466]  ? btrfs_start_transaction+0x249/0x460
[ 4372.880470]  ? btrfs_sync_file+0x288/0x3c0
[ 4372.880475]  ? btrfs_file_write_iter+0x3a9/0x4e0
[ 4372.880479]  ? vfs_write+0x26c/0x2c0
[ 4372.880483]  ? SyS_write+0x3d/0xa0
[ 4372.880486]  ? SyS_fchown+0x7b/0xa0
[ 4372.880491]  ? entry_SYSCALL_64_fastpath+0x13/0x94
[ 4372.880508] kworker/u8:8    D    0   759      2 0x00000000
[ 4372.880518] Workqueue: btrfs-submit btrfs_submit_helper
[ 4372.880520] Call Trace:
[ 4372.880524]  ? __schedule+0x160/0x7c0
[ 4372.880529]  ? io_schedule+0x64/0xe0
[ 4372.880534]  ? blk_mq_get_tag+0x212/0x320
[ 4372.880538]  ? wake_bit_function+0x60/0x60
[ 4372.880544]  ? __blk_mq_alloc_request+0x11/0x1c0
[ 4372.880548]  ? blk_mq_sched_get_request+0x17e/0x220
[ 4372.880553]  ? blk_sq_make_request+0xd3/0x4c0
[ 4372.880557]  ? blk_mq_sched_dispatch_requests+0x104/0x160
[ 4372.880561]  ? generic_make_request+0xc3/0x2e0
[ 4372.880564]  ? submit_bio+0x58/0x100
[ 4372.880569]  ? run_scheduled_bios+0x1a6/0x500
[ 4372.880574]  ? btrfs_worker_helper+0x129/0x1c0
[ 4372.880580]  ? process_one_work+0x1bc/0x400
[ 4372.880585]  ? worker_thread+0x42/0x540
[ 4372.880588]  ? __schedule+0x168/0x7c0
[ 4372.880592]  ? process_one_work+0x400/0x400
[ 4372.880596]  ? kthread+0x144/0x180
[ 4372.880600]  ? kthread_flush_work_fn+0x20/0x20
[ 4372.880605]  ? ret_from_fork+0x23/0x30

I could get it going again by running:
 echo "mq-deadline" > /sys/block/sdb/queue/scheduler

--
Markus

[toc] | [prev] | [next] | [standalone]

#1594580 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

On 03/04/2017 09:01 AM, Paolo Valente wrote:
> @@ -560,6 +600,15 @@ struct bfq_data {
>  	struct bfq_io_cq *bio_bic;
>  	/* bfqq associated with the task issuing current bio for merging */
>  	struct bfq_queue *bio_bfqq;
> +
> +	/*
> +	 * io context to put right after bfqd->lock is released. This
> +	 * filed is used to perform put_io_context, when needed, to
> +	 * after the scheduler lock has been released, and thus
> +	 * prevent an ioc->lock from being possibly taken while the
> +	 * scheduler lock is being held.
> +	 */
> +	struct io_context *ioc_to_put;
>  };

The logic around this is nasty, effectively you end up having locking
around sections of code instea of structures, which is never a good
idea.

The helper functions for unlocking and dropping the ioc add to the mess
as well.

Can't we simply pass back a pointer to an ioc to free? That should be
possible, given that we must have grabbed the bfqd lock ourselves
further up in the call chain. So we _know_ that we'll drop it later on.
If that wasn't the case, the existing logic wouldn't work.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1601349 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

> Il giorno 07 mar 2017, alle ore 18:44, Jens Axboe <axboe@kernel.dk> ha scritto:
> 
> On 03/04/2017 09:01 AM, Paolo Valente wrote:
>> @@ -560,6 +600,15 @@ struct bfq_data {
>> 	struct bfq_io_cq *bio_bic;
>> 	/* bfqq associated with the task issuing current bio for merging */
>> 	struct bfq_queue *bio_bfqq;
>> +
>> +	/*
>> +	 * io context to put right after bfqd->lock is released. This
>> +	 * filed is used to perform put_io_context, when needed, to
>> +	 * after the scheduler lock has been released, and thus
>> +	 * prevent an ioc->lock from being possibly taken while the
>> +	 * scheduler lock is being held.
>> +	 */
>> +	struct io_context *ioc_to_put;
>> };
> 
> The logic around this is nasty, effectively you end up having locking
> around sections of code instea of structures, which is never a good
> idea.
> 
> The helper functions for unlocking and dropping the ioc add to the mess
> as well.
> 

Hi Jens,
fortunately I seem to have found and fixed the bug causing the failure
your reported in one of your previous emails, so I've started addressing
the issue you raise here.  But your suggestion below raised doubts
that I was not able to solve.  So I'm bailing out and asking for help.

> Can't we simply pass back a pointer to an ioc to free? That should be
> possible, given that we must have grabbed the bfqd lock ourselves
> further up in the call chain. So we _know_ that we'll drop it later on.
> If that wasn't the case, the existing logic wouldn't work.
> 

One of the two functions that discover that an ioc has to bee freed,
namely __bfq_bfqd_reset_in_service, is invoked at the end of several
relatively long chains of function invocations.  The heads of these
chains take and release the scheduler lock.  One example is:

bfq_dispatch_request -> __bfq_dispatch_request -> bfq_select_queue -> bfq_bfqq_expire  -> __bfq_bfqq_expire -> __bfq_bfqd_reset_in_service

To implement your proposal, all the functions involved in these chains
should be extended to pass back the ioc to put.  The resulting, heavy
version of the code seems really unadvisable, and prone to errors when
one modifies or adds some chain.

So I have certainly misunderstood something.  As usual, to help you
help me more quickly, here is a summary of what I have understood on
this matter.

1.  For similar, if not exactly the same, lock-nesting issue related
to io-context putting, deferred work is used.  Probably deferred work
is used also for other reasons, but for sure it does solve this issue too.

2.  My solution (which I'm not defending; I'm just trying to
understand) solves the same issue as above: put the io
context after the other lock is released.  But it solves it with no
work-queueing overhead.  Instead of queueing work, it 'queues' the ioc
to put, and puts it right after releasing the scheduler lock.

Where is my mistake?  And what is the correct interpretation of your
proposal to pass back the pointer (instead of storing it in a field of
the device data structure)?

Thanks,
Paolo

> -- 
> Jens Axboe
> 

[toc] | [prev] | [next] | [standalone]

#1601508 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

On 03/15/2017 06:01 AM, Paolo Valente wrote:
> 
>> Il giorno 07 mar 2017, alle ore 18:44, Jens Axboe <axboe@kernel.dk> ha scritto:
>>
>> On 03/04/2017 09:01 AM, Paolo Valente wrote:
>>> @@ -560,6 +600,15 @@ struct bfq_data {
>>> 	struct bfq_io_cq *bio_bic;
>>> 	/* bfqq associated with the task issuing current bio for merging */
>>> 	struct bfq_queue *bio_bfqq;
>>> +
>>> +	/*
>>> +	 * io context to put right after bfqd->lock is released. This
>>> +	 * filed is used to perform put_io_context, when needed, to
>>> +	 * after the scheduler lock has been released, and thus
>>> +	 * prevent an ioc->lock from being possibly taken while the
>>> +	 * scheduler lock is being held.
>>> +	 */
>>> +	struct io_context *ioc_to_put;
>>> };
>>
>> The logic around this is nasty, effectively you end up having locking
>> around sections of code instea of structures, which is never a good
>> idea.
>>
>> The helper functions for unlocking and dropping the ioc add to the mess
>> as well.
>>
> 
> Hi Jens,
> fortunately I seem to have found and fixed the bug causing the failure
> your reported in one of your previous emails, so I've started addressing
> the issue you raise here.  But your suggestion below raised doubts
> that I was not able to solve.  So I'm bailing out and asking for help.

Great (on fixing that other bug).

>> Can't we simply pass back a pointer to an ioc to free? That should be
>> possible, given that we must have grabbed the bfqd lock ourselves
>> further up in the call chain. So we _know_ that we'll drop it later on.
>> If that wasn't the case, the existing logic wouldn't work.
>>
> 
> One of the two functions that discover that an ioc has to bee freed,
> namely __bfq_bfqd_reset_in_service, is invoked at the end of several
> relatively long chains of function invocations.  The heads of these
> chains take and release the scheduler lock.  One example is:
> 
> bfq_dispatch_request -> __bfq_dispatch_request -> bfq_select_queue -> bfq_bfqq_expire  -> __bfq_bfqq_expire -> __bfq_bfqd_reset_in_service
> 
> To implement your proposal, all the functions involved in these chains
> should be extended to pass back the ioc to put.  The resulting, heavy
> version of the code seems really unadvisable, and prone to errors when
> one modifies or adds some chain.
> 
> So I have certainly misunderstood something.  As usual, to help you
> help me more quickly, here is a summary of what I have understood on
> this matter.
> 
> 1.  For similar, if not exactly the same, lock-nesting issue related
> to io-context putting, deferred work is used.  Probably deferred work
> is used also for other reasons, but for sure it does solve this issue too.
> 
> 2.  My solution (which I'm not defending; I'm just trying to
> understand) solves the same issue as above: put the io
> context after the other lock is released.  But it solves it with no
> work-queueing overhead.  Instead of queueing work, it 'queues' the ioc
> to put, and puts it right after releasing the scheduler lock.
> 
> Where is my mistake?  And what is the correct interpretation of your
> proposal to pass back the pointer (instead of storing it in a field of
> the device data structure)?

I think you understood me correctly. Currently I think the putting of
the io context is somewhat of a mess. You have seemingly random places
where you have to use special unlock functions, to ensure that you
notice that some caller deeper down has set ->ioc_to_put. I took a quick
look at it, and by far most of the cases can return an io_context to
free quite easily. You can mark these functions __must_check to ensure
that we don't drop an io_context, inadvertently. That's already a win
over the random ->ioc_to_put store. And you can then get rid of
bfq_unlock_put_ioc and it's irq variant as well.

The places where you are already returning a value, like off dispatch
for instance, you can just pass in a pointer to an io_context pointer.

If you get this right, it'll be a lot less fragile and hacky than your
current approach.

I'd avoid having to do deferred put from a workqueue at all costs. This
is an _expensive_ operation.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1601537 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

On 03/15/2017 09:47 AM, Jens Axboe wrote:
> I think you understood me correctly. Currently I think the putting of
> the io context is somewhat of a mess. You have seemingly random places
> where you have to use special unlock functions, to ensure that you
> notice that some caller deeper down has set ->ioc_to_put. I took a quick
> look at it, and by far most of the cases can return an io_context to
> free quite easily. You can mark these functions __must_check to ensure
> that we don't drop an io_context, inadvertently. That's already a win
> over the random ->ioc_to_put store. And you can then get rid of
> bfq_unlock_put_ioc and it's irq variant as well.
> 
> The places where you are already returning a value, like off dispatch
> for instance, you can just pass in a pointer to an io_context pointer.
> 
> If you get this right, it'll be a lot less fragile and hacky than your
> current approach.

Even just looking a little closer, you also find cases where you
potentially twice store ->ioc_to_put. That kind of mixup can't happen if
you return it properly.

In __bfq_dispatch_request(), for instance. You call bfq_select_queue(),
and that in turn calls bfq_bfqq_expire(), which calls
__bfq_bfqq_expire() which can set ->ioc_to_put. But later on,
__bfq_dispatch_request() calls bfq_dispatch_rq_from_bfqq(), which in
turn calls bfq_bfqq_expire() that can also set ->ioc_to_put. There's no
"magic" bfq_unlock_and_put_ioc() in-between those. Maybe the former call
never sets ->ioc_to_put if it returns with bfqq == NULL? Hard to tell.

Or __bfq_insert_request(), it calls bfq_add_request(), which may set
->ioc_to_put through bfq_bfqq_handle_idle_busy_switch() ->
bfq_bfqq_expire(). And then from calling bfq_rq_enqueued() ->
bfq_bfqq_expire().

There might be more, but I think the above is plenty of evidence that
the current ->ioc_to_put solution is a bad hack, fragile, and already
has bugs.

How often do you expect this putting of the io_context to happen? If
it's not a very frequent occurence, maybe using a deferred workqueue to
put it IS the right solution. As it currently stands, the code doesn't
really work, and it's fragile. It can't be cleaned up without
refactoring, since the call paths are all extremely intermingled.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1601575 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

> Il giorno 15 mar 2017, alle ore 17:30, Jens Axboe <axboe@kernel.dk> ha scritto:
> 
> On 03/15/2017 09:47 AM, Jens Axboe wrote:
>> I think you understood me correctly. Currently I think the putting of
>> the io context is somewhat of a mess. You have seemingly random places
>> where you have to use special unlock functions, to ensure that you
>> notice that some caller deeper down has set ->ioc_to_put. I took a quick
>> look at it, and by far most of the cases can return an io_context to
>> free quite easily. You can mark these functions __must_check to ensure
>> that we don't drop an io_context, inadvertently. That's already a win
>> over the random ->ioc_to_put store. And you can then get rid of
>> bfq_unlock_put_ioc and it's irq variant as well.
>> 
>> The places where you are already returning a value, like off dispatch
>> for instance, you can just pass in a pointer to an io_context pointer.
>> 
>> If you get this right, it'll be a lot less fragile and hacky than your
>> current approach.
> 
> Even just looking a little closer, you also find cases where you
> potentially twice store ->ioc_to_put. That kind of mixup can't happen if
> you return it properly.
> 
> In __bfq_dispatch_request(), for instance. You call bfq_select_queue(),
> and that in turn calls bfq_bfqq_expire(), which calls
> __bfq_bfqq_expire() which can set ->ioc_to_put. But later on,
> __bfq_dispatch_request() calls bfq_dispatch_rq_from_bfqq(), which in
> turn calls bfq_bfqq_expire() that can also set ->ioc_to_put. There's no
> "magic" bfq_unlock_and_put_ioc() in-between those. Maybe the former call
> never sets ->ioc_to_put if it returns with bfqq == NULL? Hard to tell.
> 
> Or __bfq_insert_request(), it calls bfq_add_request(), which may set
> ->ioc_to_put through bfq_bfqq_handle_idle_busy_switch() ->
> bfq_bfqq_expire(). And then from calling bfq_rq_enqueued() ->
> bfq_bfqq_expire().
> 

I have checked that.  Basically, since a queue can't be expired twice,
then it should never happen that ioc_to_put is set twice before being
used.  Yet, I do agree that using a shared field and exploiting
collateral effects makes code very complex and fragile (maybe even
buggy if my speculative check is wrong).  Just, it has been the best
solution I found, to avoid deferred work as you asked.  In fact, I
still find quite heavy the alternative of passing a pointer to an ioc
forth and back across seven or eight nested functions.

> There might be more, but I think the above is plenty of evidence that
> the current ->ioc_to_put solution is a bad hack, fragile, and already
> has bugs.
> 
> How often do you expect this putting of the io_context to happen?

Unfortunately often, as it must be done also every time the in-service
queue is reset.  But, in this respect, are we sure that we do need to
grab a reference to the ioc when we set a queue in service (as done in
cfq, and copied into bfq)?  I mean, we have the hook exit_ioc for
controlling the disappearing of an ioc.  Am I missing something here
too?

Thanks,
Paolo

> If
> it's not a very frequent occurence, maybe using a deferred workqueue to
> put it IS the right solution. As it currently stands, the code doesn't
> really work, and it's fragile. It can't be cleaned up without
> refactoring, since the call paths are all extremely intermingled.
> 
> -- 
> Jens Axboe
> 

[toc] | [prev] | [next] | [standalone]

#1601739 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

On 03/15/2017 10:59 AM, Paolo Valente wrote:
> 
>> Il giorno 15 mar 2017, alle ore 17:30, Jens Axboe <axboe@kernel.dk> ha scritto:
>>
>> On 03/15/2017 09:47 AM, Jens Axboe wrote:
>>> I think you understood me correctly. Currently I think the putting of
>>> the io context is somewhat of a mess. You have seemingly random places
>>> where you have to use special unlock functions, to ensure that you
>>> notice that some caller deeper down has set ->ioc_to_put. I took a quick
>>> look at it, and by far most of the cases can return an io_context to
>>> free quite easily. You can mark these functions __must_check to ensure
>>> that we don't drop an io_context, inadvertently. That's already a win
>>> over the random ->ioc_to_put store. And you can then get rid of
>>> bfq_unlock_put_ioc and it's irq variant as well.
>>>
>>> The places where you are already returning a value, like off dispatch
>>> for instance, you can just pass in a pointer to an io_context pointer.
>>>
>>> If you get this right, it'll be a lot less fragile and hacky than your
>>> current approach.
>>
>> Even just looking a little closer, you also find cases where you
>> potentially twice store ->ioc_to_put. That kind of mixup can't happen if
>> you return it properly.
>>
>> In __bfq_dispatch_request(), for instance. You call bfq_select_queue(),
>> and that in turn calls bfq_bfqq_expire(), which calls
>> __bfq_bfqq_expire() which can set ->ioc_to_put. But later on,
>> __bfq_dispatch_request() calls bfq_dispatch_rq_from_bfqq(), which in
>> turn calls bfq_bfqq_expire() that can also set ->ioc_to_put. There's no
>> "magic" bfq_unlock_and_put_ioc() in-between those. Maybe the former call
>> never sets ->ioc_to_put if it returns with bfqq == NULL? Hard to tell.
>>
>> Or __bfq_insert_request(), it calls bfq_add_request(), which may set
>> ->ioc_to_put through bfq_bfqq_handle_idle_busy_switch() ->
>> bfq_bfqq_expire(). And then from calling bfq_rq_enqueued() ->
>> bfq_bfqq_expire().
>>
> 
> I have checked that.  Basically, since a queue can't be expired twice,
> then it should never happen that ioc_to_put is set twice before being
> used.  Yet, I do agree that using a shared field and exploiting
> collateral effects makes code very complex and fragile (maybe even
> buggy if my speculative check is wrong).  Just, it has been the best
> solution I found, to avoid deferred work as you asked.  In fact, I
> still find quite heavy the alternative of passing a pointer to an ioc
> forth and back across seven or eight nested functions.

It's not heavy at all, I went through all of it this morning. It's not
super pretty either, since you end up passing back an io_context which
is seemingly unrelated to what the functions otherwise do. But that's
mostly a reflection of the implementation, not that it's a bad way to go
about this in general. The worst bits are the places where you want to
add a

	WARN_ON(ret != NULL);

between two calls that potentially both drop the ioc. In terms of
overhead, it's not heavy. Punting to a workqueue would be orders of
magnitude more expensive.

>> There might be more, but I think the above is plenty of evidence that
>> the current ->ioc_to_put solution is a bad hack, fragile, and already
>> has bugs.
>>
>> How often do you expect this putting of the io_context to happen?
> 
> Unfortunately often, as it must be done also every time the in-service
> queue is reset.  But, in this respect, are we sure that we do need to
> grab a reference to the ioc when we set a queue in service (as done in
> cfq, and copied into bfq)?  I mean, we have the hook exit_ioc for
> controlling the disappearing of an ioc.  Am I missing something here
> too?

No, in fact that'd be perfectly fine. It's easier for CFQ to just retain
the reference so we know it's not going away, but for your case, it
might in fact make more sense to simply be able to de-service a queue if
the process exits. And if you do that, we can drop all this passing back
of ioc (or ->ioc_to_put) craziness, without having to punt to a
workqueue either.

This will be more efficient too, since it'll be a much more rare
occurence.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1603759 — Re: [PATCH RFC 10/14] block, bfq: add Early Queue Merge (EQM)

> Il giorno 15 mar 2017, alle ore 21:00, Jens Axboe <axboe@kernel.dk> ha scritto:
> 
> On 03/15/2017 10:59 AM, Paolo Valente wrote:
>> 
>>> Il giorno 15 mar 2017, alle ore 17:30, Jens Axboe <axboe@kernel.dk> ha scritto:
>>> 
>>> On 03/15/2017 09:47 AM, Jens Axboe wrote:
>>>> I think you understood me correctly. Currently I think the putting of
>>>> the io context is somewhat of a mess. You have seemingly random places
>>>> where you have to use special unlock functions, to ensure that you
>>>> notice that some caller deeper down has set ->ioc_to_put. I took a quick
>>>> look at it, and by far most of the cases can return an io_context to
>>>> free quite easily. You can mark these functions __must_check to ensure
>>>> that we don't drop an io_context, inadvertently. That's already a win
>>>> over the random ->ioc_to_put store. And you can then get rid of
>>>> bfq_unlock_put_ioc and it's irq variant as well.
>>>> 
>>>> The places where you are already returning a value, like off dispatch
>>>> for instance, you can just pass in a pointer to an io_context pointer.
>>>> 
>>>> If you get this right, it'll be a lot less fragile and hacky than your
>>>> current approach.
>>> 
>>> Even just looking a little closer, you also find cases where you
>>> potentially twice store ->ioc_to_put. That kind of mixup can't happen if
>>> you return it properly.
>>> 
>>> In __bfq_dispatch_request(), for instance. You call bfq_select_queue(),
>>> and that in turn calls bfq_bfqq_expire(), which calls
>>> __bfq_bfqq_expire() which can set ->ioc_to_put. But later on,
>>> __bfq_dispatch_request() calls bfq_dispatch_rq_from_bfqq(), which in
>>> turn calls bfq_bfqq_expire() that can also set ->ioc_to_put. There's no
>>> "magic" bfq_unlock_and_put_ioc() in-between those. Maybe the former call
>>> never sets ->ioc_to_put if it returns with bfqq == NULL? Hard to tell.
>>> 
>>> Or __bfq_insert_request(), it calls bfq_add_request(), which may set
>>> ->ioc_to_put through bfq_bfqq_handle_idle_busy_switch() ->
>>> bfq_bfqq_expire(). And then from calling bfq_rq_enqueued() ->
>>> bfq_bfqq_expire().
>>> 
>> 
>> I have checked that.  Basically, since a queue can't be expired twice,
>> then it should never happen that ioc_to_put is set twice before being
>> used.  Yet, I do agree that using a shared field and exploiting
>> collateral effects makes code very complex and fragile (maybe even
>> buggy if my speculative check is wrong).  Just, it has been the best
>> solution I found, to avoid deferred work as you asked.  In fact, I
>> still find quite heavy the alternative of passing a pointer to an ioc
>> forth and back across seven or eight nested functions.
> 
> It's not heavy at all, I went through all of it this morning.

Yes, sorry. I meant heavy in terms of code complexity.

> It's not
> super pretty either, since you end up passing back an io_context which
> is seemingly unrelated to what the functions otherwise do.

Exactly.

> But that's
> mostly a reflection of the implementation, not that it's a bad way to go
> about this in general. The worst bits are the places where you want to
> add a
> 
> 	WARN_ON(ret != NULL);
> 
> between two calls that potentially both drop the ioc. In terms of
> overhead, it's not heavy. Punting to a workqueue would be orders of
> magnitude more expensive.
> 
>>> There might be more, but I think the above is plenty of evidence that
>>> the current ->ioc_to_put solution is a bad hack, fragile, and already
>>> has bugs.
>>> 
>>> How often do you expect this putting of the io_context to happen?
>> 
>> Unfortunately often, as it must be done also every time the in-service
>> queue is reset.  But, in this respect, are we sure that we do need to
>> grab a reference to the ioc when we set a queue in service (as done in
>> cfq, and copied into bfq)?  I mean, we have the hook exit_ioc for
>> controlling the disappearing of an ioc.  Am I missing something here
>> too?
> 
> No, in fact that'd be perfectly fine. It's easier for CFQ to just retain
> the reference so we know it's not going away, but for your case, it
> might in fact make more sense to simply be able to de-service a queue if
> the process exits. And if you do that, we can drop all this passing back
> of ioc (or ->ioc_to_put) craziness, without having to punt to a
> workqueue either.
> 

Done, and ... well, it seems to work :)

I'm striving to have a new patch series ready before Monday, but I'm
not confident I'll make it.

Thanks,
Paolo

> This will be more efficient too, since it'll be a much more rare
> occurence.
> 
> -- 
> Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1594719 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

> +/**
> + * bfq_entity_of - get an entity from a node.
> + * @node: the node field of the entity.
> + *
> + * Convert a node pointer to the relative entity.  This is used only
> + * to simplify the logic of some functions and not as the generic
> + * conversion mechanism because, e.g., in the tree walking functions,
> + * the check for a %NULL value would be redundant.
> + */
> +static struct bfq_entity *bfq_entity_of(struct rb_node *node)
> +{
> +	struct bfq_entity *entity = NULL;
> +
> +	if (node)
> +		entity = rb_entry(node, struct bfq_entity, rb_node);
> +
> +	return entity;
> +}

Get rid of pointless wrappers like this, just use rb_entry() in the
caller. It's harmful to the readability of the code to have to lookup
things like this, if it's a list_entry or rb_entry() in the caller you
know exactly what is going on immediately.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1603784 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

> Il giorno 07 mar 2017, alle ore 18:22, Jens Axboe <axboe@kernel.dk> ha scritto:
> 
>> +/**
>> + * bfq_entity_of - get an entity from a node.
>> + * @node: the node field of the entity.
>> + *
>> + * Convert a node pointer to the relative entity.  This is used only
>> + * to simplify the logic of some functions and not as the generic
>> + * conversion mechanism because, e.g., in the tree walking functions,
>> + * the check for a %NULL value would be redundant.
>> + */
>> +static struct bfq_entity *bfq_entity_of(struct rb_node *node)
>> +{
>> +	struct bfq_entity *entity = NULL;
>> +
>> +	if (node)
>> +		entity = rb_entry(node, struct bfq_entity, rb_node);
>> +
>> +	return entity;
>> +}
> 
> Get rid of pointless wrappers like this, just use rb_entry() in the
> caller. It's harmful to the readability of the code to have to lookup
> things like this, if it's a list_entry or rb_entry() in the caller you
> know exactly what is going on immediately.
> 


Ok.  Just a quick request for help about this.  The code seems to become
quite ugly with a verbatim replacement of this function with its body
(and there are several occurrences of it), so there is probably something I'm
missing.  For example, given the following loop:

	for (; entity ; entity = bfq_entity_of(rb_first(active)))
		bfq_reparent_leaf_entity(bfqd, entity);

the only non-cryptic, but heavier solution I see is:

	for (; entity ; ) {
		bfq_reparent_leaf_entity(bfqd, entity);
		if (rb_first(active))
			entity = rb_entry(rb_first(active), struct bfq_entity, rb_node);
		else
			entity = NULL;
	}

Am I missing something?  Or are these extra lines of code a reasonable
price to pay for increased transparency?

Thanks,
Paolo

> -- 
> Jens Axboe
> 

[toc] | [prev] | [next] | [standalone]

#1600461 — Re: [PATCH RFC 01/14] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler

> Il giorno 06 mar 2017, alle ore 20:40, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
> 

Hi Bart,
thanks for such an accurate review.  I'm addressing the issues you
raised, and I'll get back in touch as soon as I have finished.

Paolo

> On 03/04/2017 08:01 AM, Paolo Valente wrote:
>> BFQ is a proportional-share I/O scheduler, whose general structure,
>> plus a lot of code, are borrowed from CFQ.
>> [ ... ]
> 
> This description is very useful. However, since it is identical to the
> description this patch adds to Documentation/block/bfq-iosched.txt I
> propose to leave it out from the patch description.
> 
> What seems missing to me is an overview of the limitations of BFQ. Does
> BFQ e.g. support multiple hardware queues?
> 
>> +3. What are BFQ's tunable?
>> +==========================
>> +[ ... ]
> 
> A thorough knowledge of BFQ is required to tune it properly. Users don't
> want to tune I/O schedulers. Has it been considered to invent algorithms
> to tune these parameters automatically?
> 
>> + * Licensed under GPL-2.
> 
> The COPYING file at the top of the tree mentions that GPL-v2 licensing
> should be specified as follows close to the start of each source file:
> 
>    This program is free software; you can redistribute it and/or modify
>    it under the terms of the GNU General Public License as published by
>    the Free Software Foundation; either version 2 of the License, or
>    (at your option) any later version.
> 
>    This program is distributed in the hope that it will be useful,
>    but WITHOUT ANY WARRANTY; without even the implied warranty of
>    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>    GNU General Public License for more details.
> 
>    You should have received a copy of the GNU General Public License
>    along with this program; if not, write to the Free Software
>    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
>    02110-1301 USA
> 
>> + * BFQ is a proportional-share I/O scheduler, with some extra
>> + * low-latency capabilities. BFQ also supports full hierarchical
>> + * scheduling through cgroups. Next paragraphs provide an introduction
>> + * on BFQ inner workings. Details on BFQ benefits and usage can be
>> + * found in Documentation/block/bfq-iosched.txt.
> 
> That reference should be sufficient - please do not duplicate
> Documentation/block/bfq-iosched.txt in block/bfq-iosched.c.
> 
>> +/**
>> + * struct bfq_service_tree - per ioprio_class service tree.
>> + *
>> + * Each service tree represents a B-WF2Q+ scheduler on its own.  Each
>> + * ioprio_class has its own independent scheduler, and so its own
>> + * bfq_service_tree.  All the fields are protected by the queue lock
>> + * of the containing bfqd.
>> + */
>> +struct bfq_service_tree {
>> +	/* tree for active entities (i.e., those backlogged) */
>> +	struct rb_root active;
>> +	/* tree for idle entities (i.e., not backlogged, with V <= F_i)*/
>> +	struct rb_root idle;
>> +
>> +	struct bfq_entity *first_idle;	/* idle entity with minimum F_i */
>> +	struct bfq_entity *last_idle;	/* idle entity with maximum F_i */
>> +
>> +	u64 vtime; /* scheduler virtual time */
>> +	/* scheduler weight sum; active and idle entities contribute to it */
>> +	unsigned long wsum;
>> +};
> 
> Inline comments next to structure members are ugly and make the
> structure definition hard to read. Please follow the instructions in
> Documentation/kernel-doc-nano-HOWTO.txt for documenting structure members.
> 
>> +	u64 finish; /* B-WF2Q+ finish timestamp (aka F_i) */
>> +	u64 start;  /* B-WF2Q+ start timestamp (aka S_i) */
> 
> For all times and timestamps, please document the time unit (e.g. s, ms,
> us, ns, jiffies, ...).
> 
>> +enum bfq_device_speed {
>> +	BFQ_BFQD_FAST,
>> +	BFQ_BFQD_SLOW,
>> +};
> 
> What is the meaning of "fast" and "slow" devices in this context?
> Anyway, since the first patch that uses this enum is patch 6, please
> defer introduction of this enum until patch 6.
> 
>> +
>> +/**
>> + * struct bfq_data - per-device data structure.
>> + *
>> + * All the fields are protected by @lock.
>> + */
>> +struct bfq_data {
>> +	/* device request queue */
>> +	struct request_queue *queue;
>> +	[ ... ]
>> +
>> +	/* on-disk position of the last served request */
>> +	sector_t last_position;
> 
> What is the relevance of last_position if there are multiple hardware
> queues? Will the BFQ algorithm fail to realize its guarantees in that case?
> 
> What is the relevance of this structure member for block devices that
> have multiple spindles, e.g. arrays of hard disks?
> 
>> +enum bfqq_state_flags {
>> +	BFQ_BFQQ_FLAG_busy = 0,		/* has requests or is in service */
>> +	BFQ_BFQQ_FLAG_wait_request,	/* waiting for a request */
>> +	BFQ_BFQQ_FLAG_non_blocking_wait_rq, /*
>> +					     * waiting for a request
>> +					     * without idling the device
>> +					     */
>> +	BFQ_BFQQ_FLAG_fifo_expire,	/* FIFO checked in this slice */
>> +	BFQ_BFQQ_FLAG_idle_window,	/* slice idling enabled */
>> +	BFQ_BFQQ_FLAG_sync,		/* synchronous queue */
>> +	BFQ_BFQQ_FLAG_budget_new,	/* no completion with this budget */
>> +	BFQ_BFQQ_FLAG_IO_bound,		/*
>> +					 * bfqq has timed-out at least once
>> +					 * having consumed at most 2/10 of
>> +					 * its budget
>> +					 */
>> +};
> 
> The "BFQ_BFQQ_FLAG_" prefix looks silly and too long to me. How about
> e.g. using the prefix "BFQQF_" instead?
> 
>> +#define BFQ_BFQQ_FNS(name)						\
>> +static void bfq_mark_bfqq_##name(struct bfq_queue *bfqq)		\
>> +{									\
>> +	(bfqq)->flags |= (1 << BFQ_BFQQ_FLAG_##name);			\
>> +}									\
>> +static void bfq_clear_bfqq_##name(struct bfq_queue *bfqq)		\
>> +{									\
>> +	(bfqq)->flags &= ~(1 << BFQ_BFQQ_FLAG_##name);			\
>> +}									\
>> +static int bfq_bfqq_##name(const struct bfq_queue *bfqq)		\
>> +{									\
>> +	return ((bfqq)->flags & (1 << BFQ_BFQQ_FLAG_##name)) != 0;	\
>> +}
> 
> Are the bodies of the above functions duplicates of __set_bit(),
> __clear_bit() and test_bit()?
> 
>> +/* Expiration reasons. */
>> +enum bfqq_expiration {
>> +	BFQ_BFQQ_TOO_IDLE = 0,		/*
>> +					 * queue has been idling for
>> +					 * too long
>> +					 */
>> +	BFQ_BFQQ_BUDGET_TIMEOUT,	/* budget took too long to be used */
>> +	BFQ_BFQQ_BUDGET_EXHAUSTED,	/* budget consumed */
>> +	BFQ_BFQQ_NO_MORE_REQUESTS,	/* the queue has no more requests */
>> +	BFQ_BFQQ_PREEMPTED		/* preemption in progress */
>> +};
> 
> The prefix of these constants refers twice to "BFQ" and does not make it
> clear that these constants are about expiration. How about using the
> "BFQQE_" prefix instead?
> 
>> +/* Maximum backwards seek, in KiB. */
>> +static const int bfq_back_max = 16 * 1024;
> 
> Where does this constant come from? Should it depend on geometry data
> like e.g. the number of sectors in a cylinder?
> 
>> +#define for_each_entity(entity)	\
>> +	for (; entity ; entity = NULL)
> 
> Why has this confusing #define been introduced? Shouldn't all
> occurrences of this macro be changed into the equivalent "if (entity)"?
> We don't want silly macros like this in the Linux kernel.
> 
>> +#define for_each_entity_safe(entity, parent) \
>> +	for (parent = NULL; entity ; entity = parent)
> 
> Same question here - why has this macro been introduced and how has its
> name been chosen? Since this macro is used only once and since no value
> is assigned to 'parent' in the code controlled by this construct, please
> remove this macro and use something that is less confusing than a "for"
> loop for something that is not a loop.
> 
>> +/**
>> + * bfq_weight_to_ioprio - calc an ioprio from a weight.
>> + * @weight: the weight value to convert.
>> + *
>> + * To preserve as much as possible the old only-ioprio user interface,
>> + * 0 is used as an escape ioprio value for weights (numerically) equal or
>> + * larger than IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF.
>> + */
>> +static unsigned short bfq_weight_to_ioprio(int weight)
>> +{
>> +	return IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF - weight < 0 ?
>> +		0 : IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF - weight;
>> +}
> 
> Please consider using max() or max_t() to make this function less verbose.
> 
>> +
>> +/**
>> + * bfq_active_extract - remove an entity from the active tree.
>> + * @st: the service_tree containing the tree.
>> + * @entity: the entity being removed.
>> + */
>> +static void bfq_active_extract(struct bfq_service_tree *st,
>> +			       struct bfq_entity *entity)
>> +{
>> +	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
>> +	struct rb_node *node;
>> +
>> +	node = bfq_find_deepest(&entity->rb_node);
>> +	bfq_extract(&st->active, entity);
>> +
>> +	if (node)
>> +		bfq_update_active_tree(node);
>> +
>> +	if (bfqq)
>> +		list_del(&bfqq->bfqq_list);
>> +}
> 
> Which locks protect the data structures manipulated by this and other
> functions? Have you considered to use lockdep_assert_held() to document
> these assumptions?
> 
>> +	case (BFQ_RQ1_WRAP|BFQ_RQ2_WRAP): /* both rqs wrapped */
> 
> Please don't use parentheses if no confusion is possible. Additionally,
> checkpatch should have requested you to insert a space before and after
> the logical or operator.
> 
>> +static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
>> +				       struct bfq_queue *bfqq)
>> +{
>> +	if (bfqq) {
>> +		bfq_mark_bfqq_budget_new(bfqq);
>> +		bfq_clear_bfqq_fifo_expire(bfqq);
>> +
>> +		bfqd->budgets_assigned = (bfqd->budgets_assigned*7 + 256) / 8;
> 
> Checkpatch should have asked you to insert spaces around the
> multiplication operator.
> 
>> +/*
>> + * bfq_default_budget - return the default budget for @bfqq on @bfqd.
>> + * @bfqd: the device descriptor.
>> + * @bfqq: the queue to consider.
>> + *
>> + * We use 3/4 of the @bfqd maximum budget as the default value
>> + * for the max_budget field of the queues.  This lets the feedback
>> + * mechanism to start from some middle ground, then the behavior
>> + * of the process will drive the heuristics towards high values, if
>> + * it behaves as a greedy sequential reader, or towards small values
>> + * if it shows a more intermittent behavior.
>> + */
>> +static unsigned long bfq_default_budget(struct bfq_data *bfqd,
>> +					struct bfq_queue *bfqq)
>> +{
>> +	unsigned long budget;
>> +
>> +	/*
>> +	 * When we need an estimate of the peak rate we need to avoid
>> +	 * to give budgets that are too short due to previous measurements.
>> +	 * So, in the first 10 assignments use a ``safe'' budget value.
>> +	 */
>> +	if (bfqd->budgets_assigned < 194 && bfqd->bfq_user_max_budget == 0)
>> +		budget = bfq_default_max_budget;
>> +	else
>> +		budget = bfqd->bfq_max_budget;
>> +
>> +	return budget - budget / 4;
>> +}
> 
> Where does the magic constant "194" come from?
> 
> 
>> +	} else
>> +		/*
>> +		 * Async queues get always the maximum possible
>> +		 * budget, as for them we do not care about latency
>> +		 * (in addition, their ability to dispatch is limited
>> +		 * by the charging factor).
>> +		 */
>> +		budget = bfqd->bfq_max_budget;
>> +
> 
> Please balance braces. Checkpatch should have warned about the use of "}
> else" instead of "} else {".
> 
>> +static unsigned long bfq_calc_max_budget(u64 peak_rate, u64 timeout)
>> +{
>> +	unsigned long max_budget;
>> +
>> +	/*
>> +	 * The max_budget calculated when autotuning is equal to the
>> +	 * amount of sectors transferred in timeout at the
>> +	 * estimated peak rate.
>> +	 */
>> +	max_budget = (unsigned long)(peak_rate * 1000 *
>> +				     timeout >> BFQ_RATE_SHIFT);
>> +
>> +	return max_budget;
>> +}
> 
> Where does the constant 1000 come from? What are the units of peak_rate
> and timeout? What is the maximum value of peak_rate? Can the
> multiplication overflow?
> 
>> +/*
>> + * In addition to updating the peak rate, checks whether the process
>> + * is "slow", and returns 1 if so. This slow flag is used, in addition
>> + * to the budget timeout, to reduce the amount of service provided to
>> + * seeky processes, and hence reduce their chances to lower the
>> + * throughput. See the code for more details.
>> + */
>> +static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
>> +				 bool compensate)
>> +{
>> +	u64 bw, usecs, expected, timeout;
>> +	ktime_t delta;
>> +	int update = 0;
>> +
>> +	if (!bfq_bfqq_sync(bfqq) || bfq_bfqq_budget_new(bfqq))
>> +		return false;
>> +
>> +	if (compensate)
>> +		delta = bfqd->last_idling_start;
>> +	else
>> +		delta = ktime_get();
>> +	delta = ktime_sub(delta, bfqd->last_budget_start);
>> +	usecs = ktime_to_us(delta);
>> +
>> +	/* Don't trust short/unrealistic values. */
>> +	if (usecs < 100 || usecs >= LONG_MAX)
>> +		return false;
> 
> If usecs >= LONG_MAX that indicates a kernel bug. Please consider
> triggering a kernel warning in that case.
> 
>> +/*
>> + * Budget timeout is not implemented through a dedicated timer, but
>> + * just checked on request arrivals and completions, as well as on
>> + * idle timer expirations.
>> + */
>> +static bool bfq_bfqq_budget_timeout(struct bfq_queue *bfqq)
>> +{
>> +	if (bfq_bfqq_budget_new(bfqq) ||
>> +	    time_before(jiffies, bfqq->budget_timeout))
>> +		return false;
>> +	return true;
>> +}
> 
> Have you considered to use time_is_after_jiffies() instead of
> time_before(jiffies, ...)?
> 
>> +static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
>> +			  struct bfq_io_cq *bic, pid_t pid, int is_sync)
>> +{
>> +	RB_CLEAR_NODE(&bfqq->entity.rb_node);
>> +	INIT_LIST_HEAD(&bfqq->fifo);
>> +
>> +	bfqq->ref = 0;
>> +	bfqq->bfqd = bfqd;
>> +
>> +	if (bic)
>> +		bfq_set_next_ioprio_data(bfqq, bic);
>> +
>> +	if (is_sync) {
>> +		if (!bfq_class_idle(bfqq))
>> +			bfq_mark_bfqq_idle_window(bfqq);
>> +		bfq_mark_bfqq_sync(bfqq);
>> +	} else
>> +		bfq_clear_bfqq_sync(bfqq);
>> +
>> +	bfqq->ttime.last_end_request = ktime_get_ns() - (1ULL<<32);
>> +
>> +	bfq_mark_bfqq_IO_bound(bfqq);
>> +
>> +	bfqq->pid = pid;
>> +
>> +	/* Tentative initial value to trade off between thr and lat */
>> +	bfqq->max_budget = bfq_default_budget(bfqd, bfqq);
>> +	bfqq->budget_timeout = bfq_smallest_from_now();
>> +	bfqq->pid = pid;
>> +
>> +	/* first request is almost certainly seeky */
>> +	bfqq->seek_history = 1;
>> +}
> 
> What is the meaning of the 1ULL << 32 constant?
> 
>> +static int __init bfq_init(void)
>> +{
>> +	int ret;
>> +	char msg[50] = "BFQ I/O-scheduler: v0";
> 
> Please leave out "[50]" and use "static const char" instead of "char".
> 
>> diff --git a/block/elevator.c b/block/elevator.c
>> index 01139f5..786fdcd 100644
>> --- a/block/elevator.c
>> +++ b/block/elevator.c
>> @@ -221,14 +221,20 @@ int elevator_init(struct request_queue *q, char *name)
>> 
>> 	if (!e) {
>> 		/*
>> -		 * For blk-mq devices, we default to using mq-deadline,
>> -		 * if available, for single queue devices. If deadline
>> -		 * isn't available OR we have multiple queues, default
>> -		 * to "none".
>> +		 * For blk-mq devices, we default to using bfq, if
>> +		 * available, for single queue devices. If bfq isn't
>> +		 * available, we try mq-deadline. If neither is
>> +		 * available, OR we have multiple queues, default to
>> +		 * "none".
>> 		 */
>> 		if (q->mq_ops) {
>> +			if (q->nr_hw_queues == 1) {
>> +				e = elevator_get("bfq", false);
>> +				if (!e)
>> +					e = elevator_get("mq-deadline", false);
>> +			}
>> 			if (q->nr_hw_queues == 1)
>> -				e = elevator_get("mq-deadline", false);
>> +				e = elevator_get("bfq", false);
>> 			if (!e)
>> 				return 0;
>> 		} else
>> 
> 
> As Jens wrote, it's way too early to make BFQ the default scheduler.
> 
> Bart.

[toc] | [prev] | [next] | [standalone]

#1600465

> Il giorno 07 mar 2017, alle ore 01:22, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
> 
> On 03/04/2017 08:01 AM, Paolo Valente wrote:
>> Some patch generates WARNINGS with checkpatch.pl, but these WARNINGS
>> seem to be either unavoidable for the involved pieces of code (which
>> the patch just extends), or false positives.
> 
> The code in this series looks reasonably clean from a code style point
> of view,

Great, thanks!

> but please address all checkpatch warnings that can be
> addressed easily. A few examples of such checkpatch warnings:
> 
> ERROR: "foo * bar" should be "foo *bar"
> 

The offending line is:
*(__PTR) = (u64)__data * NSEC_PER_USEC;

so this seems a false positive.

> WARNING: Symbolic permissions 'S_IRUGO|S_IWUSR' are not preferred.
> Consider using octal permissions '0644'.
> 

I have used symbolic permissions because I find them much easier to
remember and decode than numeric constants, and because it is done so
in cfq-iosched.c, deadline-iosched.c and now mq-deadline.c.  But,
since you share this checkpatch complain, I will switch to constants.

Thanks,
Paolo

> Thanks,
> 
> Bart.

[toc] | [prev] | [next] | [standalone]

#1600625

> Il giorno 07 mar 2017, alle ore 02:00, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
> 
> On Sat, 2017-03-04 at 17:01 +0100, Paolo Valente wrote:
>> Finally, a few details on the patchset.
>> 
>> The first two patches introduce BFQ-v0, which is more or less the
>> first version of BFQ submitted a few years ago [1].  The remaining
>> patches turn progressively BFQ-v0 into BFQ-v8r8, the current version
>> of BFQ.
> 
> Hello Paolo,
> 

Hi Bart,

> Thank you for having done the work to improve, test, fix and post the
> BFQ scheduler as a patch series. However, from what I have seen in the
> patches there is a large number of tunable constants in the code for
> which no scientific approach exists to chose an optimal value.

I'm very sorry about that, I have exported those parameters over the
years, just as an aid for debugging and tuning.  Then I have forgot to
remove them :(

They'll disappear in my next submission.

> Additionally, the complexity of the code is huge. Just like for CFQ,
> sooner or later someone will run into a bug or a performance issue
> and will post a patch to fix it. However, the complexity of BFQ is
> such that a source code review alone won't be sufficient to verify
> whether or not such a patch negatively affects a workload or device
> that has not been tested by the author of the patch. This makes me
> wonder what process should be followed to verify future BFQ patches?
> 

I've a sort of triple reply for that.

First, I've developed BFQ in a sort of
first-the-problem-then-the-solution way.  That is, each time, I have
first implemented a benchmark that enabled me to highlight the problem
and get all relevant statistics on it, then I have worked on BFQ to
try to solve that problem, using the benchmark as a support.  All
those benchmarks are in the public S suite now.  In particular, by
running one script, and waiting at most one hour, you get graphs of
- throughput with read/write/random/sequential workloads
- start-up times of bash, xterm, gnome terminal and libreoffice, when
all the above combinations of workloads are executed in the background
- frame drop rate for the playback of a movie, again with both all the
above combinations of workloads and the recurrent start of a bash
shell in the background
- kernel-task execution times (compilation, merge, ...), again with
all the above combinations of workloads in the background
- fairness with various combinations of weights and processes
- throughput against interleaved I/O, with a number of readers ranging
from 2 to 9

Every time I fix a bug, add a new feature or port BFQ to a new kernel
version, I just run that script and compare new graphs with previous
ones.  Any regression shows up immediately.  We already have a
similar, working script for Android too, although covering only
throughput, responsiveness and frame drops for the moment.  Of course,
the coverage of these scripts is limited to only the goals for which I
have devised and tuned BFQ so far.  But I hope that it won't be too
hard to extend them to other important use cases (e.g., dbms).

Second, IMO BFQ is complex also because it contains a lot of features.
We have adopted the usual approach for handling this type of
complexity: find clean cuts to get independent pieces, and put each
piece in a separate file, plus one header glue file.  The pieces were:
scheduling engine, hierarchical-scheduling support (allowing the
engine to scheduler generic nodes in the hierarchy), cgroups support.
Yet, Tejun last year, and Jens more recently, have asked to put
everything in one file; for other good reasons of course.  If you do
think that turning back to multiple files may somehow help, and there
are no strong objections from others, then I'm willing to resume this
option and possibly find event better splits.

Third and last, a proposal: why don't we discuss this issue at LSF
too?  In particular, we could talk about the parts of BFQ that seem
more complex to understand, until they become clearer to you.  Then I
could try to understand what helped make them clearer, and translate
it into extra comments in the code or into other, more radical
changes.

Thanks,
Paolo

> Thanks,
> 
> Bart.

[toc] | [prev] | [next] | [standalone]

#1600633

On 03/14/2017 09:35 AM, Paolo Valente wrote:
> First, I've developed BFQ in a sort of
> first-the-problem-then-the-solution way.  That is, each time, I have
> first implemented a benchmark that enabled me to highlight the problem
> and get all relevant statistics on it, then I have worked on BFQ to
> try to solve that problem, using the benchmark as a support.  All
> those benchmarks are in the public S suite now.  In particular, by
> running one script, and waiting at most one hour, you get graphs of
> - throughput with read/write/random/sequential workloads
> - start-up times of bash, xterm, gnome terminal and libreoffice, when
> all the above combinations of workloads are executed in the background
> - frame drop rate for the playback of a movie, again with both all the
> above combinations of workloads and the recurrent start of a bash
> shell in the background
> - kernel-task execution times (compilation, merge, ...), again with
> all the above combinations of workloads in the background
> - fairness with various combinations of weights and processes
> - throughput against interleaved I/O, with a number of readers ranging
> from 2 to 9
> 
> Every time I fix a bug, add a new feature or port BFQ to a new kernel
> version, I just run that script and compare new graphs with previous
> ones.  Any regression shows up immediately.  We already have a
> similar, working script for Android too, although covering only
> throughput, responsiveness and frame drops for the moment.  Of course,
> the coverage of these scripts is limited to only the goals for which I
> have devised and tuned BFQ so far.  But I hope that it won't be too
> hard to extend them to other important use cases (e.g., dbms).

This is great, btw, and a really nice tool set to have when evaluating
new changes.

> Second, IMO BFQ is complex also because it contains a lot of features.
> We have adopted the usual approach for handling this type of
> complexity: find clean cuts to get independent pieces, and put each
> piece in a separate file, plus one header glue file.  The pieces were:
> scheduling engine, hierarchical-scheduling support (allowing the
> engine to scheduler generic nodes in the hierarchy), cgroups support.
> Yet, Tejun last year, and Jens more recently, have asked to put
> everything in one file; for other good reasons of course.  If you do
> think that turning back to multiple files may somehow help, and there
> are no strong objections from others, then I'm willing to resume this
> option and possibly find event better splits.
> 
> Third and last, a proposal: why don't we discuss this issue at LSF
> too?  In particular, we could talk about the parts of BFQ that seem
> more complex to understand, until they become clearer to you.  Then I
> could try to understand what helped make them clearer, and translate
> it into extra comments in the code or into other, more radical
> changes.

A big issue here is the lack of nicely structured code. It's one massive
file of code, 8751 lines, or almost 270K of code. It might be a lot
easier to read and understand if it was split into smaller files,
containing various parts of it.

-- 
Jens Axboe

[toc] | [prev] | [next] | [standalone]

#1603764

> Il giorno 14 mar 2017, alle ore 16:32, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
> 
> On Tue, 2017-03-14 at 16:35 +0100, Paolo Valente wrote:
>>> Il giorno 07 mar 2017, alle ore 02:00, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
>>> 
>>> Additionally, the complexity of the code is huge. Just like for CFQ,
>>> sooner or later someone will run into a bug or a performance issue
>>> and will post a patch to fix it. However, the complexity of BFQ is
>>> such that a source code review alone won't be sufficient to verify
>>> whether or not such a patch negatively affects a workload or device
>>> that has not been tested by the author of the patch. This makes me
>>> wonder what process should be followed to verify future BFQ patches?
>> 
>> Third and last, a proposal: why don't we discuss this issue at LSF
>> too?  In particular, we could talk about the parts of BFQ that seem
>> more complex to understand, until they become clearer to you.  Then I
>> could try to understand what helped make them clearer, and translate
>> it into extra comments in the code or into other, more radical
>> changes.
> 
> Hello Paolo,
> 
> Sorry if my comment was not clear enough. Suppose that e.g. someone would
> like to modify the following code:
> 
> static int bfq_min_budget(struct bfq_data *bfqd)
> {
>       if (bfqd->budgets_assigned < bfq_stats_min_budgets)
>               return bfq_default_max_budget / 32;
>       else
>               return bfqd->bfq_max_budget / 32;
> }
> 
> How to predict the performance impact of any changes in e.g. this function?
> It is really great that a performance benchmark is available. But what should
> a developer do who only has access to a small subset of all the storage
> devices that are supported by the Linux kernel and hence who can not run the
> benchmark against every supported storage device? Do developers who do not
> fully understand the BFQ algorithms and who run into a performance problem
> have any other option than trial and error for fixing such performance issues?
> 

Hi Bart,
maybe I got your point even before, but I did not reply consistently.
You are highlighting an important problem, which, I think, can be
stated in more general terms: if one makes a change in any complex
component, which, in its turn, interacts with complex I/O devices,
then it is hard, if ever possible, to prove, that that change will
cause no regression with any possible device, just by speculation.
Actually, facts show that this often holds even for simple components,
given the complexity of the environment in which they work.  Of
course, if not only the component is complex, but who modifies it does
not even fully understand how that component works, then regressions
on untested devices are certainly more probable.

These general considerations are the motivation for my previous
proposals: reduce complexity by breaking into simpler, independent
pieces; fix or improve documentation where needed or useful (why don't
we discuss the most obscure parts at lsfmm?); use a fixed set of
benchmarks to find regressions.  Any other proposal is more than
welcome.

Thanks,
Paolo


> Thanks,
> 
> Bart.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web