From patchwork Tue Aug 28 22:27:27 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10579223 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 686C114E1 for ; Tue, 28 Aug 2018 22:27:33 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 553532AC11 for ; Tue, 28 Aug 2018 22:27:33 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 4916F2AC1D; Tue, 28 Aug 2018 22:27:33 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE,T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2DA8F2AC11 for ; Tue, 28 Aug 2018 22:27:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D36F36B4866; Tue, 28 Aug 2018 18:27:30 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id CE5F36B4867; Tue, 28 Aug 2018 18:27:30 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B86F16B4868; Tue, 28 Aug 2018 18:27:30 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pl1-f197.google.com (mail-pl1-f197.google.com [209.85.214.197]) by kanga.kvack.org (Postfix) with ESMTP id 6F0A86B4866 for ; Tue, 28 Aug 2018 18:27:30 -0400 (EDT) Received: by mail-pl1-f197.google.com with SMTP id b93-v6so1236154plb.10 for ; Tue, 28 Aug 2018 15:27:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:dkim-signature:date:from:to:cc:subject :message-id:mime-version:content-disposition:user-agent; bh=lp8S4hSKG3FLA0vLm4/xmg/I8M2HWqNPKRGVhxCfoXs=; b=SyJfxk+3k53UZ+vPJhfcM4weFta7yp6jW0p7CEqs3/JIO0QR+tYF1AFgEdjTe/cp2D yEkfu5RcbhCuqZfqnnYSZno6TEofSk+VVX6JaKMk9F7o9N1sGjX01mDFaYev0V1FIqmL 40Ru78krPyDSrK4ZnYQjFwPOJ3m//8Qkv958HbFt2HIKySRG8lXtBDtQJna1RkIDuHCL Rxg2p6+gsAyuTrRO6zdNlqGs0wXybLQtBT2a5thrIZWcei5hrY6joUbQgYHsOg/ZWdim t/pf346Uq71kBhz8sD4YoRy+mQA0uZ5tmxM87kAIfpCTf13ADdnb5aUbUjwAh6OFzAH7 G1wg== X-Gm-Message-State: APzg51Cl3UoYFNnDJKmhFLvJ71AAontkbBKxkU8k+dFyhULAzqvwFs7j O118zov6LGa5Adxtt4AF0WmCYmAkt2bFgzcFTMfMhglhrkt5KbmRmm8QerUWdgOU/bkPn3gSCoo EvBDU58xJ1H132TpN+v0OIS083dHwafFd7RY2IJK3MvGuXf3wsGndCOSPhnOJVfaMNg== X-Received: by 2002:a63:d244:: with SMTP id t4-v6mr3180572pgi.335.1535495250074; Tue, 28 Aug 2018 15:27:30 -0700 (PDT) X-Google-Smtp-Source: ANB0VdaP6+1VK6xEvTYfT5smYr6SblY17kpmAPaIj25g7UMztRhWnaD7R99z7fsM29mgiKQUcCQ2 X-Received: by 2002:a63:d244:: with SMTP id t4-v6mr3180527pgi.335.1535495248910; Tue, 28 Aug 2018 15:27:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535495248; cv=none; d=google.com; s=arc-20160816; b=vJ+rbAAQk5oqDtI6rqBx+LmXoNBfyV/D8dqUICVNpHoE2I469SWGAvfbsqx+ujV1m+ BL4XzYzjpaLJYP6DA3iRM6a0FxI1Gcw694gPUAhtaQY1jB3VXZEvweJqgzRp7fujEPtl bTujrFIelin831M56saHbTza2k7vyFnZyHfw18El3Jjdvij0/W5i/2oEC680f1ZfWWYX Z5Xr/o4czG15diK/VOiwWEqvMPOz7ehKE2OMX1EuZv0y5WoWmZXQxeKWbz3RGRnsMy5d ZNGwAsqJSmIx+xazh8On2IzW01JCSUU8oeSkzI96tWZA7/6Pf7PmAUgoOw/E9Oj/hOi+ m8Ig== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=user-agent:content-disposition:mime-version:message-id:subject:cc :to:from:date:dkim-signature:arc-authentication-results; bh=lp8S4hSKG3FLA0vLm4/xmg/I8M2HWqNPKRGVhxCfoXs=; b=VKiCF8y5nb9M30QgT5Eoa2QeoIdbhz389LcHFOdU0eTSSt4XA8uQmudYtbUnczZnaJ nfwkrsrGMMIZQpJ9age6puLP1gCYWpC4KnzGsuFleHw5X2ENM0V4BdCJcA4D3tAjHn3g 7AgoJDuMQE5U3T8S3/UvDuFLGkG1L8XGlNTgYG8R4RdGCDVP01f/p/+iqAvqgfagYp5G KN3nb+Ilg9Ht16LrE6PlWbWSPSykAUfwJc45Qmzx/95TDJHBND5+x5rquOc5lI65vo0G DFdtgOAuKa7AdAkfybmil0+y1CSwYddz5dL2d8EsJ/CdX0meyV/SpUdSg8LKeVFOAhqa Wlow== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@infradead.org header.s=bombadil.20170209 header.b=iXuhemIl; spf=pass (google.com: best guess record for domain of willy@infradead.org designates 2607:7c80:54:e::133 as permitted sender) smtp.mailfrom=willy@infradead.org Received: from bombadil.infradead.org (bombadil.infradead.org. [2607:7c80:54:e::133]) by mx.google.com with ESMTPS id t18-v6si1954789plo.191.2018.08.28.15.27.28 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 28 Aug 2018 15:27:28 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of willy@infradead.org designates 2607:7c80:54:e::133 as permitted sender) client-ip=2607:7c80:54:e::133; Authentication-Results: mx.google.com; dkim=pass header.i=@infradead.org header.s=bombadil.20170209 header.b=iXuhemIl; spf=pass (google.com: best guess record for domain of willy@infradead.org designates 2607:7c80:54:e::133 as permitted sender) smtp.mailfrom=willy@infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=Content-Type:MIME-Version: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:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=lp8S4hSKG3FLA0vLm4/xmg/I8M2HWqNPKRGVhxCfoXs=; b=iXuhemIl/aqHX8nTV6a3RmdOCD nIrQvG1iN/NB741SohCatVqqqlujnL2zxr2ZvdsdAkqGqb3YZeVc9233ApnO0QMeydTHApQJTo4le CR+xbPN9MaXiACgpr4eADJG5J/gt1DdfIrTCGU00wa43C1fTOPv/6msmayfQFv8ZRDUWb4zsau1I9 WirYKRM+D0i7k1MmaENymDVLffeV914Q6TMxil1MBvW3jZlw+vJkgUY/FZbQ3SCSzpSq8ahmDGn8I DM8vBLZQC1EpXkDQy3EuJuShznQDncv8QutUeeJcC8sGTyWilRmRTbhnWnVecJDxbyTU/DmjxjC7o 29kemgkA==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1fumSN-0008HJ-UA; Tue, 28 Aug 2018 22:27:27 +0000 Date: Tue, 28 Aug 2018 15:27:27 -0700 From: Matthew Wilcox To: linux-kernel@vger.kernel.org, linux-mm@kvack.org, linux-fsdevel@vger.kernel.org Cc: Gao Xiang , zhong jiang , Chao Yu , Greg Kroah-Hartman Subject: Tagged pointers in the XArray Message-ID: <20180828222727.GD11400@bombadil.infradead.org> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.9.2 (2017-12-15) 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: X-Virus-Scanned: ClamAV using ClamSMTP I find myself caught between two traditions. On the one hand, the radix tree has been calling the page cache dirty & writeback bits "tags" for over a decade. On the other hand, using some of the bits _in a pointer_ as a tag has been common practice since at least the 1960s. https://en.wikipedia.org/wiki/Tagged_pointer and https://en.wikipedia.org/wiki/31-bit EROFS wants to use tagged pointers in the radix tree / xarray. Right now, they're building them by hand, which is predictably grotty-looking. I think it's reasonable to provide this functionality as part of the XArray API, _but_ it's confusing to have two different things called tags. I've done my best to document my way around this, but if we want to rename the things that the radix tree called tags to avoid the problem entirely, now is the time to do it. Anybody got a Good Idea? commit e2f06dd921a072bcc021fc7224a216d2c1b88b54 Author: Matthew Wilcox Date: Tue Aug 28 14:37:22 2018 -0400 xarray: Add support for tagged pointers EROFS wants to tag its pointers rather than use XArray tags. This is a new usecase which seems reasonable to support. Signed-off-by: Matthew Wilcox diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index bc0c43f49efe..215bd468cae7 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -41,6 +41,12 @@ When you retrieve an entry from the XArray, you can check whether it is a value entry by calling :c:func:`xa_is_value`, and convert it back to an integer by calling :c:func:`xa_to_value`. +Some users want to tag their pointers without using the tag bits described +above. They can call :c:func:`xa_tag_pointer` to create an entry with +a tag, :c:func:`xa_untag_pointer` to turn a tagged entry back into an +untagged pointer and :c:func:`xa_pointer_tag` to retrieve the tag of +an entry. + The XArray does not support storing :c:func:`IS_ERR` pointers as some conflict with value entries or internal entries. diff --git a/drivers/staging/erofs/Kconfig b/drivers/staging/erofs/Kconfig index 96f614934df1..663b755bf2fb 100644 --- a/drivers/staging/erofs/Kconfig +++ b/drivers/staging/erofs/Kconfig @@ -2,7 +2,7 @@ config EROFS_FS tristate "EROFS filesystem support" - depends on BROKEN + depends on BLOCK help EROFS(Enhanced Read-Only File System) is a lightweight read-only file system with modern designs (eg. page-sized diff --git a/drivers/staging/erofs/utils.c b/drivers/staging/erofs/utils.c index 595cf90af9bb..bdee9bd09f11 100644 --- a/drivers/staging/erofs/utils.c +++ b/drivers/staging/erofs/utils.c @@ -35,7 +35,6 @@ static atomic_long_t erofs_global_shrink_cnt; #ifdef CONFIG_EROFS_FS_ZIP -/* radix_tree and the future XArray both don't use tagptr_t yet */ struct erofs_workgroup *erofs_find_workgroup( struct super_block *sb, pgoff_t index, bool *tag) { @@ -47,9 +46,8 @@ struct erofs_workgroup *erofs_find_workgroup( rcu_read_lock(); grp = radix_tree_lookup(&sbi->workstn_tree, index); if (grp != NULL) { - *tag = radix_tree_exceptional_entry(grp); - grp = (void *)((unsigned long)grp & - ~RADIX_TREE_EXCEPTIONAL_ENTRY); + *tag = xa_pointer_tag(grp); + grp = xa_untag_pointer(grp); if (erofs_workgroup_get(grp, &oldcount)) { /* prefer to relax rcu read side */ @@ -83,9 +81,7 @@ int erofs_register_workgroup(struct super_block *sb, sbi = EROFS_SB(sb); erofs_workstn_lock(sbi); - if (tag) - grp = (void *)((unsigned long)grp | - 1UL << RADIX_TREE_EXCEPTIONAL_SHIFT); + grp = xa_tag_pointer(grp, tag); err = radix_tree_insert(&sbi->workstn_tree, grp->index, grp); @@ -131,9 +127,7 @@ unsigned long erofs_shrink_workstation(struct erofs_sb_info *sbi, for (i = 0; i < found; ++i) { int cnt; - struct erofs_workgroup *grp = (void *) - ((unsigned long)batch[i] & - ~RADIX_TREE_EXCEPTIONAL_ENTRY); + struct erofs_workgroup *grp = xa_untag_pointer(batch[i]); first_index = grp->index + 1; @@ -150,8 +144,8 @@ unsigned long erofs_shrink_workstation(struct erofs_sb_info *sbi, #endif continue; - if (radix_tree_delete(&sbi->workstn_tree, - grp->index) != grp) { + if (xa_untag_pointer(radix_tree_delete(&sbi->workstn_tree, + grp->index)) != grp) { #ifdef EROFS_FS_HAS_MANAGED_CACHE skip: erofs_workgroup_unfreeze(grp, 1); diff --git a/include/linux/xarray.h b/include/linux/xarray.h index c74556ea4258..d1b383f3063f 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -24,7 +24,7 @@ * * 00: Pointer entry * 10: Internal entry - * x1: Value entry + * x1: Value entry or tagged pointer * * Attempting to store internal entries in the XArray is a bug. * @@ -150,6 +150,54 @@ static inline int xa_err(void *entry) return 0; } +/** + * xa_tag_pointer() - Create an XArray entry for a tagged pointer. + * @p: Plain pointer. + * @tag: Tag value (0, 1 or 3). + * + * If the user of the XArray prefers, they can tag their pointers instead + * of storing value entries. Three tags are available (0, 1 and 3). + * These are distinct from the xa_tag_t as they are not replicated up + * through the array and cannot be searched for. + * + * Context: Any context. + * Return: An XArray entry. + */ +static inline void *xa_tag_pointer(void *p, unsigned long tag) +{ + return (void *)((unsigned long)p | tag); +} + +/** + * xa_untag_pointer() - Turn an XArray entry into a plain pointer. + * @entry: XArray entry. + * + * If you have stored a tagged pointer in the XArray, call this function + * to get the untagged version of the pointer. + * + * Context: Any context. + * Return: A pointer. + */ +static inline void *xa_untag_pointer(void *entry) +{ + return (void *)((unsigned long)entry & ~3UL); +} + +/** + * xa_pointer_tag() - Get the tag stored in an XArray entry. + * @entry: XArray entry. + * + * If you have stored a tagged pointer in the XArray, call this function + * to get the tag of that pointer. + * + * Context: Any context. + * Return: A tag. + */ +static inline unsigned int xa_pointer_tag(void *entry) +{ + return (unsigned long)entry & 3UL; +} + typedef unsigned __bitwise xa_tag_t; #define XA_TAG_0 ((__force xa_tag_t)0U) #define XA_TAG_1 ((__force xa_tag_t)1U)