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=-7.3 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,MENTIONS_GIT_HOSTING, SPF_PASS,USER_AGENT_MUTT autolearn=ham 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 B761DC43381 for ; Mon, 18 Mar 2019 18:18:14 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 893A62133D for ; Mon, 18 Mar 2019 18:18:14 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="Rw00JWo8" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726777AbfCRSSO (ORCPT ); Mon, 18 Mar 2019 14:18:14 -0400 Received: from bombadil.infradead.org ([198.137.202.133]:44792 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726703AbfCRSSN (ORCPT ); Mon, 18 Mar 2019 14:18:13 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=In-Reply-To:Content-Type:MIME-Version :References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=UoEdlDphg4ls7xIqsXt0ESma8XJbq6j4W5f3Oxi3Mj8=; b=Rw00JWo8wYqFnnxrvx4Q9im+o FyFvOjxOgIN3Ob7u1BYkjCE2657m/zbagwEEm6Nnncm1AeT3GuhDuXQGuqPtubwQfDioBlsrQWr1B dSEsjt20Zc9W/NZbkYeuPnQlKccG8wTki1LBJho9VuEvNdHUUewo/9XMiZAHh3cPk6C1qkHuyKZAC 9rphlwdj20OBzK2qbOVkTiS7LV47/8WeCijlK1fYHobBgcwToHLL7wa4jSTFUQdV+M8uL+X0hFB53 Unp6glqq8uM1TF53zTWVfxHlErcpiHBMWQgnBnLrpYgS7uzOfOH95EBnveinx0de+QX87MsrnhU0I lhvs0jr+g==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1h5wpv-000576-Vn; Mon, 18 Mar 2019 18:18:11 +0000 Date: Mon, 18 Mar 2019 11:18:11 -0700 From: Matthew Wilcox To: Manfred Spraul Cc: Davidlohr Bueso , Waiman Long , linux-fsdevel@vger.kernel.org, 1vier1@web.de Subject: Re: xas_prev() on an idr tree? idr_get_prev()? Message-ID: <20190318181811.GQ19508@bombadil.infradead.org> References: <09bbe629-0621-c51b-111b-6168adef9731@colorfullife.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <09bbe629-0621-c51b-111b-6168adef9731@colorfullife.com> User-Agent: Mutt/1.9.2 (2017-12-15) Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org On Mon, Mar 18, 2019 at 06:36:25PM +0100, Manfred Spraul wrote: > the ipc code needs to find the highest index allocated in an idr tree. > It is part of the user space API: The return value of semctl(), msgctl() for > ..._INFO contains that number. > > Right now, the number is updated by calling idr_find(--idx), until this > succeeds. > (ipc_rmid() in ipc/util.c). > > Is there a a standard function already? > > Should I create a patch that adds idr_get_prev() to the idr API? Oof, please don't add to the IDR API. I've actually got a tree with all existing users of the IDR and radix tree APIs converted to the XArray. http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv (currently rebasing it on -rc1, checking over each patch for bugs before sending them off to the maintainers). Unfortunately, I didn't try to make ipc_rmid any smarter than it already is. That is, it currently looks like: @@ -433,7 +425,7 @@ void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp) { int idx = ipcid_to_idx(ipcp->id); - idr_remove(&ids->ipcs_idr, idx); + xa_erase(&ids->ipcs, idx); ipc_kht_remove(ids, ipcp); ids->in_use--; ipcp->deleted = true; @@ -443,7 +435,7 @@ void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp) idx--; if (idx == -1) break; - } while (!idr_find(&ids->ipcs_idr, idx)); + } while (!xa_load(&ids->ipcs, idx)); ids->max_idx = idx; } } One of the things we need is an xa_for_each_rev() macro. I think it should look like this: #define xa_for_each_rev(xa, index, entry) \ for (entry = xa_find_last(xa, &index, XA_PRESENT); \ entry; \ entry = xa_find_before(xa, &index, XA_PRESENT)) I was going to work on that at some point in the next month or so, but if you want to take it on, I'd be awfully grateful! I don't know if we need an xas_find_last() / xas_find_prev() function. Without any user that I think would benefit from it, I'd be tempted to just do the xa_ versions.