From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.3 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 32079ECE58B for ; Thu, 3 Oct 2019 21:12:08 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id CE2902133F for ; Thu, 3 Oct 2019 21:12:07 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org CE2902133F Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=stgolabs.net Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 3356E6B0005; Thu, 3 Oct 2019 17:12:07 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2EE756B0006; Thu, 3 Oct 2019 17:12:07 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 220C88E0003; Thu, 3 Oct 2019 17:12:07 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0178.hostedemail.com [216.40.44.178]) by kanga.kvack.org (Postfix) with ESMTP id F013C6B0005 for ; Thu, 3 Oct 2019 17:12:06 -0400 (EDT) Received: from smtpin20.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with SMTP id 8EC74180AD801 for ; Thu, 3 Oct 2019 21:12:06 +0000 (UTC) X-FDA: 76003721052.20.screw75_125e14c492a48 X-HE-Tag: screw75_125e14c492a48 X-Filterd-Recvd-Size: 2863 Received: from mx1.suse.de (mx2.suse.de [195.135.220.15]) by imf19.hostedemail.com (Postfix) with ESMTP for ; Thu, 3 Oct 2019 21:12:06 +0000 (UTC) X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 6E09AAF2A; Thu, 3 Oct 2019 21:12:04 +0000 (UTC) Date: Thu, 3 Oct 2019 14:10:50 -0700 From: Davidlohr Bueso To: Matthew Wilcox Cc: akpm@linux-foundation.org, walken@google.com, peterz@infradead.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, dri-devel@lists.freedesktop.org, linux-rdma@vger.kernel.org Subject: Re: [PATCH -next 00/11] lib/interval-tree: move to half closed intervals Message-ID: <20191003211050.5xwndt7ua4gw4tfq@linux-p48b> Mail-Followup-To: Matthew Wilcox , akpm@linux-foundation.org, walken@google.com, peterz@infradead.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, dri-devel@lists.freedesktop.org, linux-rdma@vger.kernel.org References: <20191003201858.11666-1-dave@stgolabs.net> <20191003203250.GE32665@bombadil.infradead.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: <20191003203250.GE32665@bombadil.infradead.org> User-Agent: NeoMutt/20180716 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Thu, 03 Oct 2019, Matthew Wilcox wrote: >On Thu, Oct 03, 2019 at 01:18:47PM -0700, Davidlohr Bueso wrote: >> It has been discussed[1,2] that almost all users of interval trees would better >> be served if the intervals were actually not [a,b], but instead [a, b). This > >So how does a user represent a range from ULONG_MAX to ULONG_MAX now? I would assume that any such lookups would be stab queries (anon/vma interval tree). So both anon and files. And yeah, I blissfully ignored any overflow scenarios. This should at least be documented. > >I think the problem is that large parts of the kernel just don't consider >integer overflow. Because we write in C, it's natural to write: > > for (i = start; i < end; i++) > >and just assume that we never need to hit ULONG_MAX or UINT_MAX. Similarly, I did not adjust queries such as 0 to ULONG_MAX, which are actually real, then again any intersecting ranges will most likely not even be close to end. >If we're storing addresses, that's generally true -- most architectures >don't allow addresses in the -PAGE_SIZE to ULONG_MAX range (or they'd >have trouble with PTR_ERR). If you're looking at file sizes, that's >not true on 32-bit machines, and we've definitely seen filesystem bugs >with files nudging up on 16TB (on 32 bit with 4k page size). Or block >driver bugs with similarly sized block devices. > >So, yeah, easier to use. But damning corner cases. I agree. Thanks, Davidlohr