From patchwork Wed Jul 12 21:11:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kent Overstreet X-Patchwork-Id: 13310888 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B4808C001DE for ; Wed, 12 Jul 2023 21:12:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232887AbjGLVMp (ORCPT ); Wed, 12 Jul 2023 17:12:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37888 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232960AbjGLVMZ (ORCPT ); Wed, 12 Jul 2023 17:12:25 -0400 Received: from out-35.mta1.migadu.com (out-35.mta1.migadu.com [IPv6:2001:41d0:203:375::23]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A83942707 for ; Wed, 12 Jul 2023 14:11:48 -0700 (PDT) X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1689196306; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Xn5bEL0Ei0eSLZ8JURgH14o2MvwdOSnzFDfE6+pvE7w=; b=prIbZNwBIuXUnvpfIhn+xwtUcXR88kKXLP66oTPIigPIrhumuCLQrJduYogig9jYymAn14 RT5C0Z9Z2fgqzx9D0ZT4psDitB0sZee9ZmXMHULgGxhF2BBhrC6hk7gmEXdRUtpDGmYUD2 WSFOGJzvpU809KWy3yH6fTc3Wjs/Yw4= From: Kent Overstreet To: linux-bcachefs@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Cc: Kent Overstreet , Kent Overstreet Subject: [PATCH 18/20] lib/generic-radix-tree.c: Don't overflow in peek() Date: Wed, 12 Jul 2023 17:11:13 -0400 Message-Id: <20230712211115.2174650-19-kent.overstreet@linux.dev> In-Reply-To: <20230712211115.2174650-1-kent.overstreet@linux.dev> References: <20230712211115.2174650-1-kent.overstreet@linux.dev> MIME-Version: 1.0 X-Migadu-Flow: FLOW_OUT Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org From: Kent Overstreet When we started spreading new inode numbers throughout most of the 64 bit inode space, that triggered some corner case bugs, in particular some integer overflows related to the radix tree code. Oops. Signed-off-by: Kent Overstreet Signed-off-by: Kent Overstreet --- include/linux/generic-radix-tree.h | 6 ++++++ lib/generic-radix-tree.c | 17 ++++++++++++++--- 2 files changed, 20 insertions(+), 3 deletions(-) diff --git a/include/linux/generic-radix-tree.h b/include/linux/generic-radix-tree.h index 107613f7d7..63080822dc 100644 --- a/include/linux/generic-radix-tree.h +++ b/include/linux/generic-radix-tree.h @@ -184,6 +184,12 @@ void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t); static inline void __genradix_iter_advance(struct genradix_iter *iter, size_t obj_size) { + if (iter->offset + obj_size < iter->offset) { + iter->offset = SIZE_MAX; + iter->pos = SIZE_MAX; + return; + } + iter->offset += obj_size; if (!is_power_of_2(obj_size) && diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c index f25eb111c0..7dfa88282b 100644 --- a/lib/generic-radix-tree.c +++ b/lib/generic-radix-tree.c @@ -166,6 +166,10 @@ void *__genradix_iter_peek(struct genradix_iter *iter, struct genradix_root *r; struct genradix_node *n; unsigned level, i; + + if (iter->offset == SIZE_MAX) + return NULL; + restart: r = READ_ONCE(radix->root); if (!r) @@ -184,10 +188,17 @@ void *__genradix_iter_peek(struct genradix_iter *iter, (GENRADIX_ARY - 1); while (!n->children[i]) { + size_t objs_per_ptr = genradix_depth_size(level); + + if (iter->offset + objs_per_ptr < iter->offset) { + iter->offset = SIZE_MAX; + iter->pos = SIZE_MAX; + return NULL; + } + i++; - iter->offset = round_down(iter->offset + - genradix_depth_size(level), - genradix_depth_size(level)); + iter->offset = round_down(iter->offset + objs_per_ptr, + objs_per_ptr); iter->pos = (iter->offset >> PAGE_SHIFT) * objs_per_page; if (i == GENRADIX_ARY)