Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Subject: Re: [RFC 1/2] Eliminate over- and under-counting of io_ticks
To:     Hou Tao <houtao1@huawei.com>, Jens Axboe <axboe@kernel.dk>,
        Mikulas Patocka <mpatocka@redhat.com>,
        Mike Snitzer <snitzer@redhat.com>
Cc:     linux-block@vger.kernel.org, linux-kernel@vger.kernel.org,
        Josh Snyder <josh@code406.com>, Ming Lei <ming.lei@redhat.com>
References: <20200609040724.448519-1-joshs@netflix.com>
 <20200609040724.448519-2-joshs@netflix.com>
 <0b7e623e-2146-5e44-f486-ba9e1657f2a3@huawei.com>
From:   Josh Snyder <joshs@netflix.com>
Message-ID: <a026a60f-e319-de35-8274-fb14ada29eff@netflix.com>
Date:   Wed, 10 Jun 2020 00:26:05 -0700
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.8.0
MIME-Version: 1.0
In-Reply-To: <0b7e623e-2146-5e44-f486-ba9e1657f2a3@huawei.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Hello!

On 6/9/20 6:41 PM, Hou Tao wrote:
> Hi,
> 
> For the following case, the under-counting is still possible if io2 wins cmpxchg():
> 
>   t          0123456
>   io1        |-----|
>   io2           |--|
>   stamp      0     6
>   io_ticks   0     3

I hadn't noticed that bug. It looks like it can produce an unbounded quantity of undercount.

> However considering patch 2 tries to improve sampling rate to 1 us, the problem will gone.

Now that you mention it, the below case is also poorly handled, and will be incorrect
regardless of sampling frequency. It experiences issues both under this patch (labeled
io_ticks) and the current implementation (labeled io_ticks~):

   t          0123456
   io1        |-----|
   io2           |-|
   stamp      0    56
   io_ticks        28

   stamp~     0  3 56
   io_ticks~     1 34

I am beginning to doubt whether it is even possible to produce an algorithm that is
simultaneously unbiased and synchronization-lite. At the same time, Ming's comment on
patch 2 was leading me to wonder about the value of being synchronization-lite in the
first place. At the proposed sampling rate of 1M/s, it is unlikely that we'd ever exercise
the synchronization-free code path (and, as your case shows, incorrect). And for every
block device that I'm aware of (even the ones that return in 10us), the cost of a disk
access still completely dominates the cost of a locked CPU operation by three orders of
magnitude.

Josh