From nobody Mon Feb 9 00:51:01 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1744358138; cv=none; d=zohomail.com; s=zohoarc; b=lktasz1AjH3KUVKjV2bIAXrVjxabIV/PBAGNIT8P+j3RMF6jk+PPTwJHOM+aegnlf/5fnTvV9FL0iB5m/kq3zXXwvtZJ8WbWwOZrsERP56qFpV6AqP3HgTqr1n1vl/KIM2XP2urUERCpkSHP98pzcGh9erAipNy5BupqliT1ens= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1744358138; h=Content-Type:Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=SA9JXMeZq0Q7AJalYvUyV3B17ebPEAq0r09wkDkoj2k=; b=a2bOCI6O1INE1eg/SWWSi4k+yk7ocAlOpJs+Pxgz/uiQdDFtUEbW3nM4rxS3rUVxh0HV0NlDO4xx7ng+VHPMbYST6nDLz7muNBdwabluDSWVJNacNXKYb6aqHuPFW5Xie94M5czGAhn8dal0wXunNqznjEbDtEvSdqO/SkdNWms= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1744358138031237.58501820460958; Fri, 11 Apr 2025 00:55:38 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.946728.1344518 (Exim 4.92) (envelope-from ) id 1u39EN-00019h-9J; Fri, 11 Apr 2025 07:55:19 +0000 Received: by outflank-mailman (output) from mailman id 946728.1344518; Fri, 11 Apr 2025 07:55:19 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1u39EN-00019a-6X; Fri, 11 Apr 2025 07:55:19 +0000 Received: by outflank-mailman (input) for mailman id 946728; Fri, 11 Apr 2025 07:55:18 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1u39EM-0000vb-6c for xen-devel@lists.xenproject.org; Fri, 11 Apr 2025 07:55:18 +0000 Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [2a00:1450:4864:20::42c]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 4e63f798-16aa-11f0-9ffb-bf95429c2676; Fri, 11 Apr 2025 09:55:16 +0200 (CEST) Received: by mail-wr1-x42c.google.com with SMTP id ffacd0b85a97d-391342fc0b5so1170552f8f.3 for ; Fri, 11 Apr 2025 00:55:16 -0700 (PDT) Received: from localhost ([84.78.159.3]) by smtp.gmail.com with UTF8SMTPSA id ffacd0b85a97d-39eaf4458a8sm1246178f8f.99.2025.04.11.00.55.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 11 Apr 2025 00:55:15 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 4e63f798-16aa-11f0-9ffb-bf95429c2676 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1744358116; x=1744962916; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=SA9JXMeZq0Q7AJalYvUyV3B17ebPEAq0r09wkDkoj2k=; b=LrAZS0EoOrq9YJTdoHQ0JX2BKWNgSy8CzOvwExFwN6CFATapnTKkjYn6NT0ruSWL0p fi1ufDS0FE7NwEi+EnLk82vNS+1eumkgLkZ7iYyOJTlJpsMaF8PFjfkwTa6K5GCf1ypa Pkc8gRMfn72XgPzwn+DMs5hhpV5D4AmjhSfzs= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1744358116; x=1744962916; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=SA9JXMeZq0Q7AJalYvUyV3B17ebPEAq0r09wkDkoj2k=; b=hcAtg4x4eAx/ThwFqOtrmHf2xJLGXoeQ+OtG2wmMgUPoXOUNhjr5CQAe7XklCfQO7M g/6wLESVAizAjdWWCw/mf3N77oY/fjbw8RuOjkJwCPI/gNN9CejMfa4OWnNKXhqRDAHt +JT0Ohn0yYtVcnjjXlH4mFlQko6Ab+iYjYB6D3Xegdww2NAixWCZitGux9a84TVN+yww Y2vBEZXXCHlJ1z49WpOd9/xHUth1V8UYpEAlpEH6IOvmA04t0QzkNaBZRDGBItUsH9HY ptSezpi31c02uBQkdRb8fT/fl0sbuRg7lIWP+JwXOrAI9+365uQWnS2MZaqnfzXkh6U0 KcFQ== X-Gm-Message-State: AOJu0YwA2iFg2TMA1o3Aec2pwQMCSqgSd542Pou+TMFebupylKdZxqLV xqsCWf9tOITV9Zcbi4weCByWmj3Hc/nyjJagyKilnswa3fZ5IHyBSyoT0pZSUK2ywwlwKMAZFgp p X-Gm-Gg: ASbGncstf0yYk9Pec8TAiIdcvLxvYh8xLze6iDmRfzdlQnzntiUQvAJGyOZJ/zMMLVl W6MODQJAA1anUbRHBDU66jXskofOFJjAXfenhcHmYG+Xiy7IPpI7Lb4fnlp3WizcA6XDvbnvG/H XpcBbRxIaVD98O4pGbFIsVPQQMfYJA+/atLLKzlUQNB+DMfVkS0TLovuR52S2SJvrLvKFDRnZf6 nATzr7AwmTZ9oT2mCrxji9tTtDSi1y1W8CqltmtQFPmQqXAE+g+DW0+CBSov6hmP2j739Uk02v/ SjnJ3UUhf2Z6U3HOiRC6NOxcdmjjUodoiPrjAytRJgOgVg== X-Google-Smtp-Source: AGHT+IFAj3qs9Qnj4aJ9djTepnSLakf+wwYwqPlCcPyHHPVF9E6tRBzZSlo46eazD6P3RX6tC4FPNw== X-Received: by 2002:a05:6000:1acc:b0:390:e9b5:d69c with SMTP id ffacd0b85a97d-39ea54fd090mr1256354f8f.25.1744358115783; Fri, 11 Apr 2025 00:55:15 -0700 (PDT) From: Roger Pau Monne To: xen-devel@lists.xenproject.org Cc: Roger Pau Monne , Andrew Cooper , Anthony PERARD , Michal Orzel , Jan Beulich , Julien Grall , Stefano Stabellini Subject: [PATCH 1/2] xen/rangeset: fix incorrect subtraction Date: Fri, 11 Apr 2025 09:55:01 +0200 Message-ID: <20250411075502.19926-2-roger.pau@citrix.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250411075502.19926-1-roger.pau@citrix.com> References: <20250411075502.19926-1-roger.pau@citrix.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1744358138947019100 Given the following rangset operation: { [0, 1], [4, 5] } - { [3, 4] } The current rangeset logic will output a rangeset: { [0, 2], [5, 5] } This is incorrect, and also has the undesirable property of being bogus in a way that the resulting rangeset is expanded. Fix this by making sure the bounds are correctly checked before modifying the previous range. Fixes: 484a058c4828 ('Add auto-destructing per-domain rangeset data structu= re...') Signed-off-by: Roger Pau Monn=C3=A9 Reviewed-by: Jan Beulich --- xen/common/rangeset.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/xen/common/rangeset.c b/xen/common/rangeset.c index b75590f90744..e75871039087 100644 --- a/xen/common/rangeset.c +++ b/xen/common/rangeset.c @@ -227,7 +227,8 @@ int rangeset_remove_range( =20 if ( x->s < s ) { - x->e =3D s - 1; + if ( x->e >=3D s ) + x->e =3D s - 1; x =3D next_range(r, x); } =20 --=20 2.48.1 From nobody Mon Feb 9 00:51:01 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1744358134; cv=none; d=zohomail.com; s=zohoarc; b=ZVsuoNGEoPJlTIpYkcguUcQgx12Er+JPPHSSyDbPsfUQcpC0v1M45CCa8MESIXXwk/4GUVIrEl1T9ttJZENdD/uQXoVBc30kLBJKu8rrIwKuCOsW0HBGlOBjMUSZcBOFhnq+7eLrl6G0qF7MdRPDNdq3Yz/DGU1XVwTA1nm5wr0= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1744358134; h=Content-Type:Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=VLeBGRbpR+Ugz3QX+1XDVxNxvcj3Y6YlL0h+g0Lm8lo=; b=FjrqFsnwwF4aaxOBep3L/vbziW2XhO0auAMOsIh2RKfBYJqbaQc8lO5sAXHbTzKSxkeRrKeCD457jiG1PD30iEPxCuwPnpSchs/QGVTnmMfqZGVw/fVu9HcDG+n2Ikj+4RxyY5bobWM+ZeR+0Y9ievHVLbb1rwr/FMP76vX2+D4= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1744358134440977.6291917162284; Fri, 11 Apr 2025 00:55:34 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.946729.1344529 (Exim 4.92) (envelope-from ) id 1u39EO-0001O8-FW; Fri, 11 Apr 2025 07:55:20 +0000 Received: by outflank-mailman (output) from mailman id 946729.1344529; Fri, 11 Apr 2025 07:55:20 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1u39EO-0001Nz-Cl; Fri, 11 Apr 2025 07:55:20 +0000 Received: by outflank-mailman (input) for mailman id 946729; Fri, 11 Apr 2025 07:55:18 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1u39EM-00011Z-LO for xen-devel@lists.xenproject.org; Fri, 11 Apr 2025 07:55:18 +0000 Received: from mail-wm1-x32b.google.com (mail-wm1-x32b.google.com [2a00:1450:4864:20::32b]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 4f30c7cf-16aa-11f0-9ead-5ba50f476ded; Fri, 11 Apr 2025 09:55:17 +0200 (CEST) Received: by mail-wm1-x32b.google.com with SMTP id 5b1f17b1804b1-43cef035a3bso11569715e9.1 for ; Fri, 11 Apr 2025 00:55:17 -0700 (PDT) Received: from localhost ([84.78.159.3]) by smtp.gmail.com with UTF8SMTPSA id 5b1f17b1804b1-43f20a9f14csm48344365e9.1.2025.04.11.00.55.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 11 Apr 2025 00:55:16 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 4f30c7cf-16aa-11f0-9ead-5ba50f476ded DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1744358117; x=1744962917; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=VLeBGRbpR+Ugz3QX+1XDVxNxvcj3Y6YlL0h+g0Lm8lo=; b=jxuewF/5MbacNom56ggBB0lYXM1qMoR9JINwhO2aAbnA8SRgdatJ5P1u4cc+oNqu3r pWFHDTjgtbDKRq2O64Mvvfg5RAT3QJUYeArc6Pu8i7c5ZgfHKC4GYG6zeaj0AacQU9kX DS3ekqOB7clYC6ckNijhFNSZozIoJaAHTXem4= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1744358117; x=1744962917; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=VLeBGRbpR+Ugz3QX+1XDVxNxvcj3Y6YlL0h+g0Lm8lo=; b=Yqwj7zmIvyRevTIysJeMUfJjVO3ilczDLIaJUyESNSqdODyp6hVwPI3blb7U8I/ytQ WSAdF8K1NzYDClhvZHHK2XGebkxt9du7Op10tMVJSpai+mNO6jXGVjz0aWlmCHymYIRO 6EClkmOcVWQWOVw+B354qU0aZr5i7CdQRuAMs1QayRq5ARFK4pfMIISF2jMLSVVmX/Ow meYB2UeGUpu+J2+EtdfNxU0Zm+PHAn2MGENK7uR7ZmYPtx8mc9Ve6UkNo/4XYyATyve4 r5HPsGlcQ63eUn6QY1llTFHXmhzDK6F6HmIG+LYnPv+Yh10+MBL3IVSdFKuim97Fn0Ys cS6w== X-Gm-Message-State: AOJu0YytFtsQavvheldKV6HVtA2QqqVUomZYas1mSA38rN+vQ72A2535 NFfpiGAT54czqfEi9eJ2K6GAjsNNqpXqjF5NRYom8SE6aZ0A12Xr+MBaYlGMNfCI6TgZ9q/6Yro X X-Gm-Gg: ASbGncuNIbhQ3KmQYMkRVCqic53nAPaQbuaRyNjKUNoebAWAfdlJbOt3dcNZjQBLFcU lroQVW5jAlvu6avlFtOPCm4khzYpIWv9zQH0qi5zpStopmDgJDo8xn7BCPxX/NcEf+A7Wtxttx4 EXmjSP0Xo8pxA4H0UZlSZ1wygEeGtvi/TC1pUX1e6+ZZVV/UXzsTRqTAcgjOyO6ZrGXcW8TJcUM JvJotlad8XzdHFqCQJBaVYdlo8BvyGlwDZZqtAmq7jd5rL9dECt5acJkOwdShrxI9/rZL4tHzHO BN2wpVgRqlPz7kFwj5YIfYZ36ZyiIClwxWG+4z5md+6bDQ== X-Google-Smtp-Source: AGHT+IGTfA53GKCinZww3+bx9Jg5VRFQcHOrdt46mfg4+BbZDjySAq8hi2RFPtvJVENwix4kBbIvpA== X-Received: by 2002:a05:600c:4e47:b0:43a:b8eb:9e5f with SMTP id 5b1f17b1804b1-43f3a9276a6mr14450305e9.3.1744358116924; Fri, 11 Apr 2025 00:55:16 -0700 (PDT) From: Roger Pau Monne To: xen-devel@lists.xenproject.org Cc: Roger Pau Monne , Anthony PERARD Subject: [PATCH 2/2] tootls/tests: introduce unit tests for rangesets Date: Fri, 11 Apr 2025 09:55:02 +0200 Message-ID: <20250411075502.19926-3-roger.pau@citrix.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250411075502.19926-1-roger.pau@citrix.com> References: <20250411075502.19926-1-roger.pau@citrix.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1744358137171019100 Introduce some basic infrastructure for doing rangeset unit tests, and add a few tests that ensure correctness of rangeset subtraction. Signed-off-by: Roger Pau Monn=C3=A9 Reviewed-by: Jan Beulich --- tools/tests/Makefile | 1 + tools/tests/rangeset/Makefile | 45 ++++++ tools/tests/rangeset/harness.h | 71 +++++++++ tools/tests/rangeset/test-rangeset.c | 228 +++++++++++++++++++++++++++ 4 files changed, 345 insertions(+) create mode 100644 tools/tests/rangeset/Makefile create mode 100644 tools/tests/rangeset/harness.h create mode 100644 tools/tests/rangeset/test-rangeset.c diff --git a/tools/tests/Makefile b/tools/tests/Makefile index 1319c3a9d88c..3e60ab6b268d 100644 --- a/tools/tests/Makefile +++ b/tools/tests/Makefile @@ -10,6 +10,7 @@ SUBDIRS-$(CONFIG_X86) +=3D x86_emulator endif SUBDIRS-y +=3D xenstore SUBDIRS-y +=3D depriv +SUBDIRS-y +=3D rangeset SUBDIRS-y +=3D vpci SUBDIRS-y +=3D paging-mempool =20 diff --git a/tools/tests/rangeset/Makefile b/tools/tests/rangeset/Makefile new file mode 100644 index 000000000000..451f67e1920f --- /dev/null +++ b/tools/tests/rangeset/Makefile @@ -0,0 +1,45 @@ +XEN_ROOT=3D$(CURDIR)/../../.. +include $(XEN_ROOT)/tools/Rules.mk + +TARGET :=3D test-rangeset + +.PHONY: all +all: $(TARGET) + +.PHONY: run +run: $(TARGET) + ./$< + +.PHONY: clean +clean: + $(RM) -- *.o $(TARGET) $(DEPS_RM) + +.PHONY: distclean +distclean: clean + $(RM) -- *~ + +.PHONY: install +install: all + $(INSTALL_DIR) $(DESTDIR)$(LIBEXEC_BIN) + $(INSTALL_PROG) $(TARGET) $(DESTDIR)$(LIBEXEC_BIN) + +.PHONY: uninstall +uninstall: + $(RM) -- $(addprefix $(DESTDIR)$(LIBEXEC_BIN)/,$(TARGET)) + +list.h: $(XEN_ROOT)/xen/include/xen/list.h +rangeset.h: $(XEN_ROOT)/xen/include/xen/rangeset.h +list.h rangeset.h: + sed -e '/#include/d' <$< >$@ + +rangeset.c: $(XEN_ROOT)/xen/common/rangeset.c list.h rangeset.h + # Remove includes and add the test harness header + sed -e '/#include/d' -e '1s/^/#include "harness.h"/' <$< >$@ + +CFLAGS +=3D -D__XEN_TOOLS__ +CFLAGS +=3D $(APPEND_CFLAGS) +CFLAGS +=3D $(CFLAGS_xeninclude) +LDFLAGS +=3D $(APPEND_LDFLAGS) + +test-rangeset: rangeset.o test-rangeset.o + $(CC) $^ -o $@ $(LDFLAGS) diff --git a/tools/tests/rangeset/harness.h b/tools/tests/rangeset/harness.h new file mode 100644 index 000000000000..a60ebff72d0f --- /dev/null +++ b/tools/tests/rangeset/harness.h @@ -0,0 +1,71 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* + * Unit tests for rangesets. + * + * Copyright (C) 2025 Cloud Software Group + */ + +#ifndef _TEST_HARNESS_ +#define _TEST_HARNESS_ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#define smp_wmb() +#define __must_check __attribute__((__warn_unused_result__)) +#define cf_check + +#define BUG_ON(x) assert(!(x)) +#define ASSERT(x) assert(x) + +#include "list.h" +#include "rangeset.h" + +typedef bool rwlock_t; +typedef bool spinlock_t; + +struct domain { + unsigned int domain_id; + struct list_head rangesets; + spinlock_t rangesets_lock; +}; + +/* For rangeset_domain_{initialize,printk}() */ +#define spin_lock_init(l) (*(l) =3D false) +#define spin_lock(l) (*(l) =3D true) +#define spin_unlock(l) (*(l) =3D false) + +/* For rangeset->lock */ +#define rwlock_init(l) (*(l) =3D false) +#define read_lock(l) (*(l) =3D true) +#define read_unlock(l) (*(l) =3D false) +#define write_lock(l) (*(l) =3D true) +#define write_unlock(l) (*(l) =3D false) + +#define xmalloc(type) ((type *)malloc(sizeof(type))) +#define xfree free + +#define unlikely + +#define safe_strcpy strcpy + +#define printk printf + +#endif + +/* + * Local variables: + * mode: C + * c-file-style: "BSD" + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + */ diff --git a/tools/tests/rangeset/test-rangeset.c b/tools/tests/rangeset/te= st-rangeset.c new file mode 100644 index 000000000000..b44cd217a050 --- /dev/null +++ b/tools/tests/rangeset/test-rangeset.c @@ -0,0 +1,228 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* + * Unit tests for rangesets. + * + * Copyright (C) 2025 Cloud Software Group + */ + +#include "harness.h" + +struct range { + unsigned long start, end; +}; + +struct action { + enum { + ADD, + REMOVE, + } action; + struct range r; +}; + +#define DECLARE_ACTIONS(nr) static const struct action actions ## nr [] +#define DECLARE_RESULTS(nr) static const struct range results ## nr [] + +/* + * Subtract range with tail overlap on existing range: + * + * { 0, 1, 4, 5 } - { 3, 4 } =3D { 0, 1, 5, 5 } + */ +DECLARE_ACTIONS(0) =3D { + { ADD, { 0, 1 } }, + { ADD, { 4, 5 } }, + { REMOVE, { 3, 4 } }, +}; +DECLARE_RESULTS(0) =3D { + { 0, 1 }, { 5, 5 }, +}; + +/* + * Subtract range with complete and tail overlap on existing ranges: + * + * { 0, 1, 4, 5, 7, 8 } - { 3, 4, 5, 6, 7 } =3D { 0, 1, 8 } + */ +DECLARE_ACTIONS(1) =3D { + { ADD, { 0, 1 } }, + { ADD, { 4, 5 } }, + { ADD, { 7, 8 } }, + { REMOVE, { 3, 7 } }, +}; +DECLARE_RESULTS(1) =3D { + { 0, 1 }, { 8, 8 }, +}; + +/* + * Subtract range with no overlap: + * + * { 0, 1, 4, 5 } - { 2, 3 } =3D { 0, 1, 4, 5 } + */ +DECLARE_ACTIONS(2) =3D { + { ADD, { 0, 1 } }, + { ADD, { 4, 5 } }, + { REMOVE, { 2, 3 } }, +}; +DECLARE_RESULTS(2) =3D { + { 0, 1 }, { 4, 5 }, +}; + +/* + * Subtract range with partial overlap on two existing ranges: + * + * { 0, 1, 4, 5 } - { 1, 4 } =3D { 0, 5 } + */ +DECLARE_ACTIONS(3) =3D { + { ADD, { 0, 1 } }, + { ADD, { 4, 5 } }, + { REMOVE, { 1, 4 } }, +}; +DECLARE_RESULTS(3) =3D { + { 0, 0 }, { 5, 5 }, +}; + +static const struct test { + unsigned int nr_actions, nr_results; + const struct action *actions; + const struct range *result; +} tests[] =3D { +#define DECLARE_TEST(nr) \ + { \ + .actions =3D actions ## nr, \ + .nr_actions =3D ARRAY_SIZE(actions ## nr), \ + .result =3D results ## nr, \ + .nr_results =3D ARRAY_SIZE(results ## nr), \ + } + + DECLARE_TEST(0), + DECLARE_TEST(1), + DECLARE_TEST(2), + DECLARE_TEST(3), + +#undef DECLARE_TEST +}; + +static int print_range(unsigned long s, unsigned long e, void *data) +{ + printf("[%ld, %ld]\n", s, e); + + return 0; +} + +static int count_ranges(unsigned long s, unsigned long e, void *data) +{ + unsigned int *nr =3D data; + + ++*nr; + return 0; +} + +const struct range *expected; +static int check_ranges(unsigned long s, unsigned long e, void *data) +{ + unsigned int *nr =3D data; + int rc =3D 0; + + if ( s !=3D expected[*nr].start || e !=3D expected[*nr].end ) + rc =3D -EINVAL; + + ++*nr; + return rc; +} + +static void print_both(struct rangeset *r, const struct range *expected, + unsigned int nr_expected) +{ + unsigned int i; + + printf("Result:\n"); + rangeset_report_ranges(r, 0, ~0UL, print_range, NULL); + printf("Expected:\n"); + for ( i =3D 0; i < nr_expected; i++ ) + printf("[%ld, %ld]\n", expected[i].start, expected[i].end); +} + +int main(int argc, char **argv) +{ + struct rangeset *r =3D rangeset_new(NULL, NULL, 0); + unsigned int i; + int ret_code =3D 0; + + ASSERT(r); + + for ( i =3D 0 ; i < ARRAY_SIZE(tests); i++ ) + { + unsigned int j, nr =3D 0; + int rc =3D 0; + + rangeset_purge(r); + for ( j =3D 0; j < tests[i].nr_actions; j++ ) + { + const struct action *a =3D &tests[i].actions[j]; + + switch ( a->action ) + { + case ADD: + rc =3D rangeset_add_range(r, a->r.start, a->r.end); + break; + + case REMOVE: + rc =3D rangeset_remove_range(r, a->r.start, a->r.end); + break; + } + + if ( rc ) + { + printf("Test %u failed to %s range [%ld, %ld]\n", + i, a->action =3D=3D ADD ? "add" : "remove", + a->r.start, a->r.end); + rangeset_report_ranges(r, 0, ~0UL, print_range, NULL); + break; + } + } + + if ( rc ) + { + /* Action failed, skip this test and set exit code to failure.= */ + ret_code =3D EXIT_FAILURE; + continue; + } + + rc =3D rangeset_report_ranges(r, 0, ~0UL, count_ranges, &nr); + if ( rc ) + { + printf("Test %u unable to count number of result ranges\n", i); + rangeset_report_ranges(r, 0, ~0UL, print_range, NULL); + ret_code =3D EXIT_FAILURE; + continue; + } + if ( nr !=3D tests[i].nr_results ) + { + printf("Test %u unexpected number of result ranges, expected: = %u got: %u\n", + i, tests[i].nr_results, nr); + print_both(r, tests[i].result, tests[i].nr_results); + ret_code =3D EXIT_FAILURE; + continue; + } + + nr =3D 0; + expected =3D tests[i].result; + rc =3D rangeset_report_ranges(r, 0, ~0UL, check_ranges, &nr); + if ( rc ) + { + printf("Test %u range checking failed\n", i); + print_both(r, tests[i].result, tests[i].nr_results); + ret_code =3D EXIT_FAILURE; + continue; + } + } + + return 0; +} + +/* + * Local variables: + * mode: C + * c-file-style: "BSD" + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + */ --=20 2.48.1