From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-qt1-f181.google.com (mail-qt1-f181.google.com [209.85.160.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 12DB93D564D for ; Mon, 4 May 2026 14:44:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.181 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1777905892; cv=none; b=Ze6o3tMuK43jktKSpRlr9j35I5WOv6BakA6ul91WcDyCV/LVilxqm/bx+qIvIRTOyFayT2tkAz9zZoyFUCyUXHjWdbZNt6A2qWVOMJVBBjuvQ23o/z1ySMkID0z0j+ZYZKJ/b5hoyr4MYDgmghmfaMhEzaSnoO/+/JJks2jDqko= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1777905892; c=relaxed/simple; bh=kc4IhSQIw6TaIMtV5PP5FrO0n405AVaoicu7KM0HhHs=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=TkR0Sn1IeNeGDJIp8dpMhr9tiCMznRmVlMSCBBtryfZhUQl5FSdmygAVoBu7Y9XYvqzm6KL63YEV+60AO5QebwfVcHb6pEK5T8UwY5E2YwrQ32f5JI8V+YAC5S5UI8ZpUXH6P6ctZyrPKGr9CjWeBPhccMkvR7bxACwZ4PSnNQQ= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=soleen.com; spf=pass smtp.mailfrom=soleen.com; dkim=pass (2048-bit key) header.d=soleen.com header.i=@soleen.com header.b=P4N1xE8E; arc=none smtp.client-ip=209.85.160.181 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=soleen.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=soleen.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=soleen.com header.i=@soleen.com header.b="P4N1xE8E" Received: by mail-qt1-f181.google.com with SMTP id d75a77b69052e-50d87610513so42967261cf.3 for ; Mon, 04 May 2026 07:44:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=soleen.com; s=google; t=1777905890; x=1778510690; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=jMK9CbMmL+n4tiRm5m3IaX0DcVz+Sz54nDXJZPFiknU=; b=P4N1xE8EpxeuwM+ArESXLt+nYnHSImSXmh4Vo1+KqJaV03mn0E/ejEV5vy8uXEVjJO 0JVPjpY9nAQUkTVSySyONheBS1TSwfLi0svJfllnXqFvc5Cn9s0nHDmxNDLay7DyfQhU nUOrp5ywEF0Lt03h6a6sJ+GxqHlj7G/bL4ZdwCofqz1EmmJBuJAjpBTAgwG6+gPm3A0E PzpEVm1AknIkp2+ODoNNEYkqME/OpHyU+HSqW2C8WobAllCeR3ke4n0VwLwaqU26jl27 JTXfeWgJw1JYICk9NcFAZPuNKKr/DYUtO4bst3SYjYeCEYYWXHS/D0giDRFIeA3U68zk KLXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777905890; x=1778510690; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-gg:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=jMK9CbMmL+n4tiRm5m3IaX0DcVz+Sz54nDXJZPFiknU=; b=TKpSvSu73xrocCSjgtnWyawCOk79lTuR0MUJ4q8NVApd742p9blMaCPDYf4FCuunXq 1wXvIy3d4wAx6l6OWm90h11vWbgTnMiz3yHJuhzLFHxFI5ht2lXnHHNqtU11+j8MhUG3 soY/pSDYTZxhMiOrkb0aLHyhnneIfjL3d6zwH5mZy6FuvfKd2K1ceREJADZyYpoY4c5F PR9kkQLsDC9vIWcEYi0Amsac1vAlGcvHBUV2qgePhMURzYeY++KQIyaFzP9F89IvSBXN AMkUmYgqdJElbBaRj77HyZQQRzI9vMJJqhemxt9N8w/NVVOUy4Gc92vTSXUG4L5OQkPP bo0w== X-Forwarded-Encrypted: i=1; AFNElJ+nS/Zl6wYJkn/KzgYRive5UZ/frRg7Gr+npHMkxAODKU6DWAom4XfycvlR+rRHH+ibiaL465m270F30xQ=@vger.kernel.org X-Gm-Message-State: AOJu0YxD+CqZtVZ3/a9WS+sD5+LpKzP0zczRHxKcFoMHzrXQ89JW43wy s4f+gE9Kc+1qi1xm2XE0iUYv8b4dZqPMLGp3oxpvZIGIJdZ6WxNzxrtlXiCQyDo2ygM= X-Gm-Gg: AeBDiespr3rk55ez6oCInb4vl4vBtclf8gUWMY/XYfRLt36ksksPhABcO1/wkY7WM2J 2dRpK4rq0byipKG9yuRSF+EmEyvGFXAII6liUlA1xij7p/ZjyxKOo3WaoJmsqTnzARhMuZs1uuh W2kriW7lxiQREh/Am1MxE828YS2KyAnbw1mXJFya+WyyvVNVv2we8f9LVYAtLLNS0lyeuoEF870 53TDmy1KVOv9jIPOW4IX8QiWwF4utnQFjcqWF4x+bFQNEPiUH2eAmD+YZ8DG5g2b7tyEoO8zTBW pFlFe3tOaT4BBCq2OW0jdXSodvyq1pujcPh8hV85zjnwOsHmPxtb6bPM2/pxpc+T5nFZY3Bv71m L0EIoLVXLKvf2caV9kCSVIDj+0NHHpxzGhxpceb8L/+gtmqFDbkNPyE88yeMzTz46AX1jLG06SO 3cif0BfTjqOVypZLBCmxL4g8ikPGbBygFJl9H9X2Gg+H9hwFiAkzN4/+tqgkTNlQ== X-Received: by 2002:a05:622a:4206:b0:50d:6a40:692a with SMTP id d75a77b69052e-5104be7625cmr148834121cf.18.1777905889904; Mon, 04 May 2026 07:44:49 -0700 (PDT) Received: from plex ([71.181.43.54]) by smtp.gmail.com with ESMTPSA id d75a77b69052e-51040ba8acdsm100582571cf.31.2026.05.04.07.44.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 May 2026 07:44:49 -0700 (PDT) Date: Mon, 4 May 2026 14:44:48 +0000 From: Pasha Tatashin To: Pratyush Yadav Cc: Mike Rapoport , Pasha Tatashin , Alexander Graf , Muchun Song , Oscar Salvador , David Hildenbrand , Andrew Morton , Jason Miu , kexec@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH 01/12] kho: generalize radix tree APIs Message-ID: References: <20260429133928.850721-1-pratyush@kernel.org> <20260429133928.850721-2-pratyush@kernel.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260429133928.850721-2-pratyush@kernel.org> On 04-29 15:39, Pratyush Yadav wrote: > From: "Pratyush Yadav (Google)" > > The KHO radix tree is a data structure that can track the presence or > absence of an arbitrary key, with nothing inherently tied to KHO memory > preservation tracking. This was one of the design goals of the radix > tree. This was done to enable it to be re-used by other users of KHO. > > Despite that, the radix tree APIs are very closely tied to KHO memory > preservation tracking. Adding a key is done by kho_radix_add_page(), > which encodes it as a page tracking operation and takes in PFN and > order. kho_radix_del_page() does the same. These functions encode the > key internally that goes into the radix tree. kho_radix_walk_tree() does > the same by baking the PFN and order into the callback arguments. > > Generalize the APIs by taking the key directly and doing the encoding at > the callers. Rename the functions to kho_radix_add_key() and > kho_radix_del_key(). In practice, this removes a line each from the > functions and moves the encoding function call to the callers. > Similarly, update kho_radix_tree_walk_callback_t to take the key > directly. > > To keep the naming convention clearer, rename > kho_radix_{encode,decode}_key() to kho_{encode,decode}_radix_key(). > > Signed-off-by: Pratyush Yadav (Google) Reviewed-by: Pasha Tatashin > --- > include/linux/kho_radix_tree.h | 18 +++---- > kernel/liveupdate/kexec_handover.c | 76 ++++++++++++++---------------- > 2 files changed, 42 insertions(+), 52 deletions(-) > > diff --git a/include/linux/kho_radix_tree.h b/include/linux/kho_radix_tree.h > index 84e918b96e53..f368f3b9f923 100644 > --- a/include/linux/kho_radix_tree.h > +++ b/include/linux/kho_radix_tree.h > @@ -34,30 +34,24 @@ struct kho_radix_tree { > struct mutex lock; /* protects the tree's structure and root pointer */ > }; > > -typedef int (*kho_radix_tree_walk_callback_t)(phys_addr_t phys, > - unsigned int order); > +typedef int (*kho_radix_tree_walk_callback_t)(unsigned long key); > > #ifdef CONFIG_KEXEC_HANDOVER > > -int kho_radix_add_page(struct kho_radix_tree *tree, unsigned long pfn, > - unsigned int order); > - > -void kho_radix_del_page(struct kho_radix_tree *tree, unsigned long pfn, > - unsigned int order); > - > +int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key); > +void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key); > int kho_radix_walk_tree(struct kho_radix_tree *tree, > kho_radix_tree_walk_callback_t cb); > > #else /* #ifdef CONFIG_KEXEC_HANDOVER */ > > -static inline int kho_radix_add_page(struct kho_radix_tree *tree, long pfn, > - unsigned int order) > +static inline int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key) > { > return -EOPNOTSUPP; > } > > -static inline void kho_radix_del_page(struct kho_radix_tree *tree, > - unsigned long pfn, unsigned int order) { } > +static inline void kho_radix_del_key(struct kho_radix_tree *tree, > + unsigned long key) { } > > static inline int kho_radix_walk_tree(struct kho_radix_tree *tree, > kho_radix_tree_walk_callback_t cb) > diff --git a/kernel/liveupdate/kexec_handover.c b/kernel/liveupdate/kexec_handover.c > index 33fcf848ef95..ba568d34c5b4 100644 > --- a/kernel/liveupdate/kexec_handover.c > +++ b/kernel/liveupdate/kexec_handover.c > @@ -85,7 +85,7 @@ static struct kho_out kho_out = { > }; > > /** > - * kho_radix_encode_key - Encodes a physical address and order into a radix key. > + * kho_encode_radix_key - Encodes a physical address and order into a radix key. > * @phys: The physical address of the page. > * @order: The order of the page. > * > @@ -95,7 +95,7 @@ static struct kho_out kho_out = { > * > * Return: The encoded unsigned long radix key. > */ > -static unsigned long kho_radix_encode_key(phys_addr_t phys, unsigned int order) > +static unsigned long kho_encode_radix_key(phys_addr_t phys, unsigned int order) > { > /* Order bits part */ > unsigned long h = 1UL << (KHO_ORDER_0_LOG2 - order); > @@ -106,17 +106,17 @@ static unsigned long kho_radix_encode_key(phys_addr_t phys, unsigned int order) > } > > /** > - * kho_radix_decode_key - Decodes a radix key back into a physical address and order. > + * kho_decode_radix_key - Decodes a radix key back into a physical address and order. > * @key: The unsigned long key to decode. > * @order: An output parameter, a pointer to an unsigned int where the decoded > * page order will be stored. > * > - * This function reverses the encoding performed by kho_radix_encode_key(), > + * This function reverses the encoding performed by kho_encode_radix_key(), > * extracting the original physical address and page order from a given key. > * > * Return: The decoded physical address. > */ > -static phys_addr_t kho_radix_decode_key(unsigned long key, unsigned int *order) > +static phys_addr_t kho_decode_radix_key(unsigned long key, unsigned int *order) > { > unsigned int order_bit = fls64(key); > phys_addr_t phys; > @@ -144,24 +144,21 @@ static unsigned long kho_radix_get_table_index(unsigned long key, > } > > /** > - * kho_radix_add_page - Marks a page as preserved in the radix tree. > + * kho_radix_add_key - Add a key to the radix tree. > * @tree: The KHO radix tree. > - * @pfn: The page frame number of the page to preserve. > - * @order: The order of the page. > + * @key: The key to add. > * > - * This function traverses the radix tree based on the key derived from @pfn > - * and @order. It sets the corresponding bit in the leaf bitmap to mark the > - * page for preservation. If intermediate nodes do not exist along the path, > - * they are allocated and added to the tree. > + * This function traverses the radix tree based on the key provided. It sets the > + * corresponding bit in the leaf bitmap to mark the key as present. If > + * intermediate nodes do not exist along the path, they are allocated and added > + * to the tree. > * > * Return: 0 on success, or a negative error code on failure. > */ > -int kho_radix_add_page(struct kho_radix_tree *tree, > - unsigned long pfn, unsigned int order) > +int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key) > { > /* Newly allocated nodes for error cleanup */ > struct kho_radix_node *intermediate_nodes[KHO_TREE_MAX_DEPTH] = { 0 }; > - unsigned long key = kho_radix_encode_key(PFN_PHYS(pfn), order); > struct kho_radix_node *anchor_node = NULL; > struct kho_radix_node *node = tree->root; > struct kho_radix_node *new_node; > @@ -224,22 +221,19 @@ int kho_radix_add_page(struct kho_radix_tree *tree, > > return err; > } > -EXPORT_SYMBOL_GPL(kho_radix_add_page); > +EXPORT_SYMBOL_GPL(kho_radix_add_key); > > /** > - * kho_radix_del_page - Removes a page's preservation status from the radix tree. > + * kho_radix_del_key - Removes the key from the radix tree. > * @tree: The KHO radix tree. > - * @pfn: The page frame number of the page to unpreserve. > - * @order: The order of the page. > + * @key: The key to remove. > * > * This function traverses the radix tree and clears the bit corresponding to > - * the page, effectively removing its "preserved" status. It does not free > - * the tree's intermediate nodes, even if they become empty. > + * the key, effectively removing it from the tree. It does not free the tree's > + * intermediate nodes, even if they become empty. > */ > -void kho_radix_del_page(struct kho_radix_tree *tree, unsigned long pfn, > - unsigned int order) > +void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key) > { > - unsigned long key = kho_radix_encode_key(PFN_PHYS(pfn), order); > struct kho_radix_node *node = tree->root; > struct kho_radix_leaf *leaf; > unsigned int i, idx; > @@ -270,21 +264,18 @@ void kho_radix_del_page(struct kho_radix_tree *tree, unsigned long pfn, > idx = kho_radix_get_bitmap_index(key); > __clear_bit(idx, leaf->bitmap); > } > -EXPORT_SYMBOL_GPL(kho_radix_del_page); > +EXPORT_SYMBOL_GPL(kho_radix_del_key); > > static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, > unsigned long key, > kho_radix_tree_walk_callback_t cb) > { > unsigned long *bitmap = (unsigned long *)leaf; > - unsigned int order; > - phys_addr_t phys; > unsigned int i; > int err; > > for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) { > - phys = kho_radix_decode_key(key | i, &order); > - err = cb(phys, order); > + err = cb(key | i); > if (err) > return err; > } > @@ -332,15 +323,14 @@ static int __kho_radix_walk_tree(struct kho_radix_node *root, > } > > /** > - * kho_radix_walk_tree - Traverses the radix tree and calls a callback for each preserved page. > + * kho_radix_walk_tree - Traverses the radix tree and calls a callback for each key. > * @tree: A pointer to the KHO radix tree to walk. > * @cb: A callback function of type kho_radix_tree_walk_callback_t that will be > - * invoked for each preserved page found in the tree. The callback receives > - * the physical address and order of the preserved page. > + * invoked for each key in the tree. > * > * This function walks the radix tree, searching from the specified top level > - * down to the lowest level (level 0). For each preserved page found, it invokes > - * the provided callback, passing the page's physical address and order. > + * down to the lowest level (level 0). For each key found, it invokes the > + * provided callback. > * > * Return: 0 if the walk completed the specified tree, or the non-zero return > * value from the callback that stopped the walk. > @@ -365,7 +355,8 @@ static void __kho_unpreserve(struct kho_radix_tree *tree, > while (pfn < end_pfn) { > order = min(count_trailing_zeros(pfn), ilog2(end_pfn - pfn)); > > - kho_radix_del_page(tree, pfn, order); > + kho_radix_del_key(tree, kho_encode_radix_key(PFN_PHYS(pfn), > + order)); > > pfn += 1 << order; > } > @@ -498,13 +489,16 @@ static struct page *__init kho_get_preserved_page(phys_addr_t phys, > return pfn_to_page(pfn); > } > > -static int __init kho_preserved_memory_reserve(phys_addr_t phys, > - unsigned int order) > +static int __init kho_preserved_memory_reserve(unsigned long key) > { > union kho_page_info info; > struct page *page; > + unsigned int order; > + phys_addr_t phys; > u64 sz; > > + phys = kho_decode_radix_key(key, &order); > + > sz = 1 << (order + PAGE_SHIFT); > page = kho_get_preserved_page(phys, order); > > @@ -858,7 +852,8 @@ int kho_preserve_folio(struct folio *folio) > if (WARN_ON(kho_scratch_overlap(pfn << PAGE_SHIFT, PAGE_SIZE << order))) > return -EINVAL; > > - return kho_radix_add_page(tree, pfn, order); > + return kho_radix_add_key(tree, kho_encode_radix_key(PFN_PHYS(pfn), > + order)); > } > EXPORT_SYMBOL_GPL(kho_preserve_folio); > > @@ -876,7 +871,7 @@ void kho_unpreserve_folio(struct folio *folio) > const unsigned long pfn = folio_pfn(folio); > const unsigned int order = folio_order(folio); > > - kho_radix_del_page(tree, pfn, order); > + kho_radix_del_key(tree, kho_encode_radix_key(PFN_PHYS(pfn), order)); > } > EXPORT_SYMBOL_GPL(kho_unpreserve_folio); > > @@ -916,7 +911,8 @@ int kho_preserve_pages(struct page *page, unsigned long nr_pages) > while (pfn_to_nid(pfn) != pfn_to_nid(pfn + (1UL << order) - 1)) > order--; > > - err = kho_radix_add_page(tree, pfn, order); > + err = kho_radix_add_key(tree, kho_encode_radix_key(PFN_PHYS(pfn), > + order)); > if (err) { > failed_pfn = pfn; > break; > -- > 2.54.0.545.g6539524ca2-goog >