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=-8.4 required=3.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,USER_IN_DEF_DKIM_WL 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 6521FC47404 for ; Fri, 4 Oct 2019 13:15:29 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 25F5D21D81 for ; Fri, 4 Oct 2019 13:15:29 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="aVs4zyKI" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 25F5D21D81 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=google.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id AECAB6B0003; Fri, 4 Oct 2019 09:15:28 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A9DEC6B0005; Fri, 4 Oct 2019 09:15:28 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9B3F58E0003; Fri, 4 Oct 2019 09:15:28 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0051.hostedemail.com [216.40.44.51]) by kanga.kvack.org (Postfix) with ESMTP id 7C19E6B0003 for ; Fri, 4 Oct 2019 09:15:28 -0400 (EDT) Received: from smtpin13.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay04.hostedemail.com (Postfix) with SMTP id 2B4D783E3 for ; Fri, 4 Oct 2019 13:15:28 +0000 (UTC) X-FDA: 76006148736.13.rub89_86fdad86e0d43 X-HE-Tag: rub89_86fdad86e0d43 X-Filterd-Recvd-Size: 5650 Received: from mail-yb1-f177.google.com (mail-yb1-f177.google.com [209.85.219.177]) by imf29.hostedemail.com (Postfix) with ESMTP for ; Fri, 4 Oct 2019 13:15:27 +0000 (UTC) Received: by mail-yb1-f177.google.com with SMTP id w141so1537300ybe.0 for ; Fri, 04 Oct 2019 06:15:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=/UcVhX9GaoSfCR5Nzgmo8T8FLFMJ0xd65q4Shx2Kmts=; b=aVs4zyKIMELcbbp0OrZDIIRM6M9FqgqBWOj7D/V0OOVxjk/TCK1tb1H33aayEVT9Fq NOF79kJ75vl2d2aHQWCNVE3mdS8xv2agwN5v/GWtJcU0doJRauKDjzYg6Q6Aok4YYi3b mqNPN9hT3Q49dLWzDmTUjRAHeblmpVkFSji5wQrOx6/uMD4mWAJGCY15WvCoWVOEjYTY zLXisVJYNrNI9DPaiv0kVngz338cFFvM+h3OzJgZEFf8gZFZm7Iiy5tpDfP2d3CkVb0j V4Ux/4E3Ys8h0MioMBqFvf8jY+vH9oklDJ5qpoyn4dUJxko+npNTfqsfS9FFgD1YpKeU TCXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=/UcVhX9GaoSfCR5Nzgmo8T8FLFMJ0xd65q4Shx2Kmts=; b=EqdZ+fP0GlUyN/0YSu3VjWEyU3809qhcQ1KuK1ilOAMSnGHCZkvS41k2HUaTH7Jf3u rsOc7VQxX+W8nwTTHrAm62BbXLdK/fhsfMnFVleRlljwcuZsC+9Dd5BfpbbBjpXyIe/u mTC93L3i/jnAVlh/FKiTyM5nMrRwlf9iNXOj2QLGmOJWVE1m7Aibz7bxkmICubizGDNk CrAJTiDW4G4LXLfYYCcPnoVN/Bp0bbKuQwXhQVbG0RX8uLWJuXBcWLff6bkALYl97lXP 1889Tamy5L+iSQulRWDRGxgh+wgemwmm8eGOYmAhK9as8HbfwtQbjsj1QiIP2qCBBJnI 28ZA== X-Gm-Message-State: APjAAAWIIX7jOWhlKYPrthSDmRNb/7BxlUXb8eLsqp+E2/Rv8kZ6n8tH kOCHAkO0Pb2EeAhZ21ypvXuVxXj8ZK3rh+qmk4c7FA== X-Google-Smtp-Source: APXvYqzwEQFavuGTQfqs5oMner1fD3hr86iQqTMlgoG4RfUPbRmbA3D9aQz/XYkIYsRESetVSOBhZBfVuAsxsNy+MeI= X-Received: by 2002:a25:8149:: with SMTP id j9mr1749501ybm.132.1570194926383; Fri, 04 Oct 2019 06:15:26 -0700 (PDT) MIME-Version: 1.0 References: <20191003201858.11666-1-dave@stgolabs.net> <20191004002609.GB1492@ziepe.ca> In-Reply-To: <20191004002609.GB1492@ziepe.ca> From: Michel Lespinasse Date: Fri, 4 Oct 2019 06:15:11 -0700 Message-ID: Subject: Re: [PATCH -next 00/11] lib/interval-tree: move to half closed intervals To: Jason Gunthorpe Cc: Davidlohr Bueso , Andrew Morton , Peter Zijlstra , LKML , linux-mm , dri-devel@lists.freedesktop.org, linux-rdma@vger.kernel.org Content-Type: text/plain; charset="UTF-8" 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: Hi Jason, On Thu, Oct 3, 2019 at 5:26 PM Jason Gunthorpe wrote: > Hurm, this is not entirely accurate. Most users do actually want > overlapping and multiple ranges. I just studied this extensively: (Just curious, are you the person we discussed this with after the Maple Tree talk at LPC 2019 ?) I think we have two separate API problems there: - overlapping vs non-overlapping intervals (the interval tree API supports overlapping intervals, but some users are confused about this) - closed vs half-open interval definitions It looks like you have been looking mostly at the first issue, which I expect could simplify several interval tree users considerably, while Davidlohr is addressing the second issue here. > radeon_mn actually wants overlapping but seems to mis-understand the > interval_tree API and actively tries hard to prevent overlapping at > great cost and complexity. I have a patch to delete all of this and > just be overlapping. > > amdgpu_mn copied the wrongness from radeon_mn > > All the DRM drivers are basically the same here, tracking userspace > controlled VAs, so overlapping is essential > > hfi1/mmu_rb definitely needs overlapping as it is dealing with > userspace VA ranges under control of userspace. As do the other > infiniband users. Do you have a handle on what usnic is doing with its intervals ? usnic_uiom_insert_interval() has some complicated logic to avoid having overlapping intervals, which is very confusing to me. > vhost probably doesn't overlap in the normal case, but again userspace > could trigger overlap in some pathalogical case. > > The [start,last] allows the interval to cover up to ULONG_MAX. I don't > know if this is needed however. Many users are using userspace VAs > here. Is there any kernel configuration where ULONG_MAX is a valid > userspace pointer? Ie 32 bit 4G userspace? I don't know. > > Many users seemed to have bugs where they were taking a userspace > controlled start + length and converting them into a start/end for > interval tree without overflow protection (woops) > > Also I have a series already cooking to delete several of these > interval tree users, which will terribly conflict with this :\ > > Is it really necessary to make such churn for such a tiny API change? My take is that this (Davidlohr's) patch series does not necessarily need to be applied all at once - we could get the first change in (adding the interval_tree_gen.h header), and convert the first few users, without getting them all at once, as long as we have a plan for finishing the work. So, if you have cleanups in progress in some of the files, just tell us which ones and we can leave them out from the first pass. Thanks, -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.