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 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 68800C47077 for ; Thu, 18 Jan 2024 06:35:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 99C486B007B; Thu, 18 Jan 2024 01:35:56 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 94CFA6B007D; Thu, 18 Jan 2024 01:35:56 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 813FB6B0080; Thu, 18 Jan 2024 01:35:56 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 72D7F6B007B for ; Thu, 18 Jan 2024 01:35:56 -0500 (EST) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 46C208068D for ; Thu, 18 Jan 2024 06:35:56 +0000 (UTC) X-FDA: 81691471512.15.9FD748F Received: from mail-ej1-f45.google.com (mail-ej1-f45.google.com [209.85.218.45]) by imf07.hostedemail.com (Postfix) with ESMTP id 83FCA40003 for ; Thu, 18 Jan 2024 06:35:53 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=Goqo9Y+t; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf07.hostedemail.com: domain of yosryahmed@google.com designates 209.85.218.45 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1705559753; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=F6Z6wuTdIE3oI+ENMJR97SNTKTQo97xJmtmIXWm79Rs=; b=GnWO/H51SBD0StR45cx2uFkgUAJxx/dn+4s5VgjyZxsZcuM5luiwyvJMp/1i+QnEOVmsfg gvt+n0bGE9L1u41PY/i4Uw+rZ5LhEI+IxlekJD7XK+X64C3G/JgQMg1+EuSOZEY2mTVgyO J59HFzMhk9xk75Zo5KZvgl0I5XRrPzk= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=Goqo9Y+t; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf07.hostedemail.com: domain of yosryahmed@google.com designates 209.85.218.45 as permitted sender) smtp.mailfrom=yosryahmed@google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1705559753; a=rsa-sha256; cv=none; b=AEl9mGxFREBTN7IuROEXsxHMFEeaRo+IlFJWnQm28U2uTe0+Zcd2/IxnqGZWwmlx31oXaO TRyLCof0gsaCcM3qSHizvwjKhDBiza+85+f33tkbI5R0dBLVFhwGgIjFKdWXtbXPN4Thwn U33uEGfytuKJ5qZfiTDJMc78CyQd7Ck= Received: by mail-ej1-f45.google.com with SMTP id a640c23a62f3a-a298accc440so1452522766b.1 for ; Wed, 17 Jan 2024 22:35:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1705559752; x=1706164552; darn=kvack.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=F6Z6wuTdIE3oI+ENMJR97SNTKTQo97xJmtmIXWm79Rs=; b=Goqo9Y+ts7OUv/ayxvTWZNzwbMETVd2vCjxKTe0RvhCpYLOvTSIDYyDIl8/uPZU9aW DzgNefkCt2CeJt9OKO7dKuJQrQS2xCs1ugAzkf0bD6eXY1uWfIRZPI8OpXAuHVA2Xkek CWpjq3Vmf21pW6CIzVjvzwS9EkLuwsIoYj5TtRhD5GKTY/VyBACChdPZhcCuONg7GUlV 1SCn3Kw3/gAnIofekQMNyLqJsgi95OyruxEkvOlafrFuC140MdjPahtL7klkuLKsHtVq C4pt+NvBRNGMOFOyj+rCdarTKT3Vi2jsODjssLhBMoi21hCZyMPkwh+U+MppVEaLht7b gjbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705559752; x=1706164552; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=F6Z6wuTdIE3oI+ENMJR97SNTKTQo97xJmtmIXWm79Rs=; b=GaQxzQPEvyYwp+AuzkE18xrMoOno4PZUrCpu+Iywv7sASSF/2wn8329+jBNVvvzsf0 JUO6E08s7wApfQyaLps2o4v0ea5DAjSRWqBemDI5J/BqPaVDSx+MlEkmnmNCLYV9Q7xK 9eRPXC9igD4u4WrdWdfSFO+hi2g1cOKHpEeq/51K9V0wu6BIaXt+O3Sd81SykWEZWrMe meG1b+qb7mEPd1Be6Dnyfdr9DeANeLWs7eAoE/db4UNBb6bXR+mFvSsR0hDkWEx6ooUR xWoURr5Av9UhPG+RCZW2QJ9hxBuboDeKL/ImgIqVkVpizkLOb5FDevXSMpq2N44YBRwx muxg== X-Gm-Message-State: AOJu0YykUHtAa2rbYZJHP9ORY9gsIxrGIJ6i8hpOdknVNnbGN1nadvtr aIL62jIIXL+7bQPCs2Fc8tv8QdNjLVRd9faYLGiA2mhS4GG+pexmzpv9WSibssQk0z3ZKsog5ZG iZ8wn5JjF7y49i19zjBQMvBQNOV3MuTuppKaX X-Google-Smtp-Source: AGHT+IF9WPH8KBIEm47kPYtcEi3P9fns4xjGcZxGxJfXJ7F/utnKCwSy+gT6g5altMwCfW0Gh/a6MGT+qR+StuUuPZQ= X-Received: by 2002:a17:906:35d8:b0:a2d:a5b5:70ab with SMTP id p24-20020a17090635d800b00a2da5b570abmr195429ejb.100.1705559751871; Wed, 17 Jan 2024 22:35:51 -0800 (PST) MIME-Version: 1.0 References: <20240117-zswap-xarray-v1-0-6daa86c08fae@kernel.org> <20240117-zswap-xarray-v1-2-6daa86c08fae@kernel.org> In-Reply-To: <20240117-zswap-xarray-v1-2-6daa86c08fae@kernel.org> From: Yosry Ahmed Date: Wed, 17 Jan 2024 22:35:15 -0800 Message-ID: Subject: Re: [PATCH 2/2] mm: zswap.c: remove RB tree To: Chris Li Cc: Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, =?UTF-8?B?V2VpIFh177+8?= , Yu Zhao , Greg Thelen , Chun-Tse Shao , =?UTF-8?Q?Suren_Baghdasaryan=EF=BF=BC?= , Brain Geffon , Minchan Kim , Michal Hocko , Mel Gorman , Huang Ying , Nhat Pham , Johannes Weiner , Kairui Song , Zhongkun He , Kemeng Shi , Barry Song , "Matthew Wilcox (Oracle)" , "Liam R. Howlett" , Joel Fernandes , Chengming Zhou Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: 83FCA40003 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 8kzhpfcyfic56i4gwn6ft8epkzw3o4ke X-HE-Tag: 1705559753-374498 X-HE-Meta: U2FsdGVkX1+qt7GM/xxM/CmkQnQ5NbHNFnYdPDhlN4fAPUwFo4Fl+IlHJKF2g5CJtp+xrUzpX6j7FiEATM+lqTGI5ropVo0GHvaSrk9tueR+AFRujPEEPAteedZf/LZ40AFzbO/jOeKKXyYN6IiH1o/MjMiY3+m9nWNMn1xLtEfDIqOIcLE56jVHa3E8WE+TQetdda78QH2iKvL0VnsYwnAqeEQxQu7eQAaH6BUM+WFaHuqnGBrj/W0dJQGLF2gejOOyOV1FsS0anLyg7jZHRRMCDvajM5CNOrgVn3PfV+3zAci5XiEdOsJroR7RH0CrSgaKBMH6Z8nsqQ+dl1Mlht0MuYOpV+CEUReaR73WpTh7dBVJU443+yOI+aD4uf22Zq+Ct5QaEcIpDFZoJqTI/26axez0LAuMkt0fUELE0lJIOA3nhOHmJpzMcpSj8rN0ys971oHveC7qe6Y1lE96mErzkMKbMLPHvC/9h5rchJmVUV/VDDnX6J7EW08jpspB/CDWuRSUt+R0lz3bskgKBvTEpzzb1ygHyURHeHjayuB+2wyJoHwBoYwR0RXsdXX+r1QD5/boFjsEAAy2hIXn0p4WQiEtn0C9DNodgNY3c0JgV60kMDf39f5qnq5PbXHw6QFvsl+gWnHYFN55oqs6bd4Mzc94XkVnYGmj3TnbBw8a1ZWNMGgqSUG380UgpQ38mHrtLaBp2iRZYo8QCnaQ2hE5MnlDQOOSajj4J5utFYOCZF+aS4XDyK2z9gFbbsAwwxdqR8t19ejV+G3YjeTJFMQYk29mxPoSV9ZkHuF/a/5SVvcBvGPOGlq9LECIv2goMDgh98oaR1kkaNtpVP15NGgw6B+qgMGTIhfF+O3X5cJoxlDSCaru+31VWABlY8KY/WQih83ZNvqsyelR9MTQzJPtJKNaFWN+DguIiGhhb/bHgEqpERsH4qvJxRo40Ms6mgQNoOjYrfiTZgrSBLn 8/fyw+kx V139XNadqGUw/B+Yd27rxGjkEB9nUHbqGH3ajQxM2E0Qgw7UrhCfa/oaU04WdT6TGPuyIrKgBjeSNcVcZAGXEoJIMVHc8oLrg/bYiNdxaVrN+1qwlIQjG7IJGB52PrXXFWvoG0FEZweQZKbXrmszuaQ3MvtRYE8lNnN6kc+tqAlUnUsw00orWCbOYFcgehXA9UiO0u1o7tTgn89M6p2tE2FEWS5hUAAUKfOmF 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: List-Subscribe: List-Unsubscribe: > @@ -493,45 +471,47 @@ static struct zswap_entry *zswap_search(struct zswap_tree *tree, pgoff_t offset) > static int zswap_insert(struct zswap_tree *tree, struct zswap_entry *entry, > struct zswap_entry **dupentry) > { > - struct rb_root *root = &tree->rbroot; > - struct rb_node **link = &root->rb_node, *parent = NULL; > - struct zswap_entry *myentry, *old; > - pgoff_t myentry_offset, entry_offset = swp_offset(entry->swpentry); > - > - > - while (*link) { > - parent = *link; > - myentry = rb_entry(parent, struct zswap_entry, rbnode); > - myentry_offset = swp_offset(myentry->swpentry); > - if (myentry_offset > entry_offset) > - link = &(*link)->rb_left; > - else if (myentry_offset < entry_offset) > - link = &(*link)->rb_right; > - else { > - old = xa_load(&tree->xarray, entry_offset); > - BUG_ON(old != myentry); > - *dupentry = myentry; > + struct zswap_entry *e; > + pgoff_t offset = swp_offset(entry->swpentry); > + XA_STATE(xas, &tree->xarray, offset); > + > + do { > + xas_lock_irq(&xas); > + do { > + e = xas_load(&xas); > + if (xa_is_zero(e)) > + e = NULL; > + } while (xas_retry(&xas, e)); > + if (xas_valid(&xas) && e) { > + xas_unlock_irq(&xas); > + *dupentry = e; > return -EEXIST; > } > - } > - rb_link_node(&entry->rbnode, parent, link); > - rb_insert_color(&entry->rbnode, root); > - old = xa_store(&tree->xarray, entry_offset, entry, GFP_KERNEL); > - return 0; > + xas_store(&xas, entry); > + xas_unlock_irq(&xas); > + } while (xas_nomem(&xas, GFP_KERNEL)); > + return xas_error(&xas); I think using the xas_* APIs can be avoided here. The only reason we need it is that we want to check if there's an existing entry first, and return -EEXIST. However, in that case, the caller will replace it anyway (and do some operations on the dupentry): while (zswap_rb_insert(&tree->rbroot, entry, &dupentry) == -EEXIST) { WARN_ON(1); zswap_duplicate_entry++; zswap_invalidate_entry(tree, dupentry); } So I think we can do something like this in zswap_insert() instead: dupentry = xa_store(..); if (WARN_ON(dupentry)) { zswap_duplicate_entry++; zswap_invalidate_entry(tree, dupentry); } WDYT? > } > > static bool zswap_erase(struct zswap_tree *tree, struct zswap_entry *entry) > { > + struct zswap_entry *e; > pgoff_t offset = swp_offset(entry->swpentry); > - if (!RB_EMPTY_NODE(&entry->rbnode)) { > - struct zswap_entry *old; > - old = xa_erase(&tree->xarray, offset); > - BUG_ON(old != entry); > - rb_erase(&entry->rbnode, &tree->rbroot); > - RB_CLEAR_NODE(&entry->rbnode); > - return true; > - } > - return false; > + XA_STATE(xas, &tree->xarray, offset); > + > + do { > + xas_lock_irq(&xas); > + do { > + e = xas_load(&xas); > + } while (xas_retry(&xas, e)); > + if (xas_valid(&xas) && e != entry) { > + xas_unlock_irq(&xas); > + return false; > + } > + xas_store(&xas, NULL); > + xas_unlock_irq(&xas); > + } while (xas_nomem(&xas, GFP_KERNEL)); > + return !xas_error(&xas); > } Same here, I think we just want: return !!xa_erase(..); > > static struct zpool *zswap_find_zpool(struct zswap_entry *entry) > @@ -583,7 +563,6 @@ static void zswap_entry_put(struct zswap_tree *tree, > > WARN_ON_ONCE(refcount < 0); > if (refcount == 0) { > - WARN_ON_ONCE(!RB_EMPTY_NODE(&entry->rbnode)); > zswap_free_entry(entry); > } nit: the braces are no longer needed here