From nobody Mon Feb 9 08:27:55 2026 Received: from mail-pf1-f201.google.com (mail-pf1-f201.google.com [209.85.210.201]) (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 B03D52222DD for ; Fri, 4 Apr 2025 21:15:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743801318; cv=none; b=NACANcHYDOSMCBe6/0ujw+0rbtFxEa6ifd4Uph+kAshRiGVQTUeDl2JyOjoF1Ii/Zcd7lcw4yoh65Fckdjrl3rt62VQyjoPIx0Q6NQsSqWPvi3+QmkxeXCX6XKJ+thb7qteoaxQ+vqkvE16V+/pyJRDH9c7fgu8RSiwsDGYsv/E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743801318; c=relaxed/simple; bh=55FJ1JjxJzEfvUCR32CEmuDHX8lAqsLw2GiyIQNI/6o=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=ujmJ19UmC/x1JRPebW2S0sj+J/PE0mxOxShrk3cLqLnYWkpSgBktEcrJssESMyeziAo5iAc1Ly1DOj11HlWeovM8EE26N3GxfEJQS1ffa1RJMg2+Zr12ANcGlRsFTa9XKmP06CpsIAkkIPOxdimQOu7qvaDvts5K5ZDz5EfweCY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--seanjc.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=pUgg2ASs; arc=none smtp.client-ip=209.85.210.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--seanjc.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="pUgg2ASs" Received: by mail-pf1-f201.google.com with SMTP id d2e1a72fcca58-73009f59215so2987518b3a.1 for ; Fri, 04 Apr 2025 14:15:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1743801316; x=1744406116; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:reply-to:from:to:cc:subject:date:message-id:reply-to; bh=rEQ6YbC3KUJ/CgEiqQT3YCqcj84Bba/mdzyHX1dIlKQ=; b=pUgg2ASs+PFlkWR65Uy9K10Xx7g0Ejg/VlahFor9bYWRMBxbrdzhq56PqySiMY27sf oTvNc//FQB72zkuNn7okhP5ZJSjlissTqt4BB9kAM9yrh0QIMWZpvxpmMbV8qHOJ+tm9 ol2kCaLR+2adiE+Ilutjlx6UcCpdx4kIguHg7B0RmZHY1E1du6vtrZq9QitNHom2kLDz Ve7QLGx/QSwnQQ07eSKTkqqPwyWNkH2fIqunCfN6r9CHCz4jdeWp8dr3twFCYYy2WGBK ywOxGKhhoYpTEGRfrC8DahsCZU270LHUmicOjeyoEKuDE16/APpmJ5gJmEEstxszUAJO l4cQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1743801316; x=1744406116; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:reply-to:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=rEQ6YbC3KUJ/CgEiqQT3YCqcj84Bba/mdzyHX1dIlKQ=; b=faLGPuipLvzc/XO06NHNYU+U/p5y8z/0nPJkhpbAKG3tRgi6sGgTn8/Eaj0ormHnSR rLEdOSON3ZngArPiCK23XaDiIJDPL43IBtxPWi8VJ0e9M9hKSimYX8U2xIoKPQhXbcEx JTh8NZi+eUu6rElAGjt+aBkzc0FNlvJnYeB0XZZxENSzLOBIYJDsEtVD7znjIkE4mosw rmrctHLCrkKqM6JHI1mBGx7MoZe2a70YLU8AfERGv3nTpgRmiL2eSgISYAH57WY4cpFT WgyUKF97+lVNM03gy4khSRqwAIuAF/3CmYbYWkVmwBjflJWmrO84Y9OONgiAtnDWtU4o zI/Q== X-Forwarded-Encrypted: i=1; AJvYcCX5/34tKQd6/BTKVmZJfsdtREAAXlraG3otD4aV8YAdbqgCkLlFdceOPbfaDicXIanU8cVtTM6deKaW4xs=@vger.kernel.org X-Gm-Message-State: AOJu0Yx910rxBeqfudjjD+fn0E18DHNpgTcVX8HIWgDR3CtlzsVS6N4x QjPrpp++hcSz8Bq2RmPazfbXacwrw/oS2Q+/+DTSM5uf4W83+rv5k1cSCOJGw+nCLChcC6hFiGE r7A== X-Google-Smtp-Source: AGHT+IGUhjY+14rjdTSJuxJSMCqc7vFux5KSB5bEGhNoAp0wfj/KsmOLIl+ozqTri6qlvIxKd+yGGWBdPPo= X-Received: from pgbfe28.prod.google.com ([2002:a05:6a02:289c:b0:af7:3f89:85dc]) (user=seanjc job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6a20:ce43:b0:1f5:a3e8:64c1 with SMTP id adf61e73a8af0-20107c3bbadmr6045725637.0.1743801315957; Fri, 04 Apr 2025 14:15:15 -0700 (PDT) Reply-To: Sean Christopherson Date: Fri, 4 Apr 2025 14:14:49 -0700 In-Reply-To: <20250404211449.1443336-1-seanjc@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250404211449.1443336-1-seanjc@google.com> X-Mailer: git-send-email 2.49.0.504.g3bcea36a83-goog Message-ID: <20250404211449.1443336-8-seanjc@google.com> Subject: [PATCH 7/7] irqbypass: Use xarray to track producers and consumers From: Sean Christopherson To: "Michael S. Tsirkin" , Jason Wang , Paolo Bonzini , Alex Williamson Cc: kvm@vger.kernel.org, virtualization@lists.linux.dev, netdev@vger.kernel.org, linux-kernel@vger.kernel.org, Sean Christopherson , Oliver Upton , David Matlack , Like Xu , Yong He Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Track IRQ bypass produsers and consumers using an xarray to avoid the O(2n) insertion time associated with walking a list to check for duplicate entries, and to search for an partner. At low (tens or few hundreds) total producer/consumer counts, using a list is faster due to the need to allocate backing storage for xarray. But as count creeps into the thousands, xarray wins easily, and can provide several orders of magnitude better latency at high counts. E.g. hundreds of nanoseconds vs. hundreds of milliseconds. Cc: Oliver Upton Cc: David Matlack Cc: Like Xu Reported-by: Yong He Closes: https://bugzilla.kernel.org/show_bug.cgi?id=3D217379 Link: https://lore.kernel.org/all/20230801115646.33990-1-likexu@tencent.com Signed-off-by: Sean Christopherson Reviewed-by: Kevin Tian --- include/linux/irqbypass.h | 2 -- virt/lib/irqbypass.c | 68 +++++++++++++++++++-------------------- 2 files changed, 34 insertions(+), 36 deletions(-) diff --git a/include/linux/irqbypass.h b/include/linux/irqbypass.h index 6d4e4882843c..e9d9485eaf99 100644 --- a/include/linux/irqbypass.h +++ b/include/linux/irqbypass.h @@ -46,7 +46,6 @@ struct irq_bypass_consumer; * for a physical device assigned to a VM. */ struct irq_bypass_producer { - struct list_head node; void *token; struct irq_bypass_consumer *consumer; int irq; @@ -73,7 +72,6 @@ struct irq_bypass_producer { * portions of the interrupt handling to the VM. */ struct irq_bypass_consumer { - struct list_head node; void *token; struct irq_bypass_producer *producer; =20 diff --git a/virt/lib/irqbypass.c b/virt/lib/irqbypass.c index 261ef77f6364..3f7734e63d0f 100644 --- a/virt/lib/irqbypass.c +++ b/virt/lib/irqbypass.c @@ -22,8 +22,8 @@ MODULE_LICENSE("GPL v2"); MODULE_DESCRIPTION("IRQ bypass manager utility module"); =20 -static LIST_HEAD(producers); -static LIST_HEAD(consumers); +static DEFINE_XARRAY(producers); +static DEFINE_XARRAY(consumers); static DEFINE_MUTEX(lock); =20 /* @lock must be held when calling connect */ @@ -86,13 +86,13 @@ static void __disconnect(struct irq_bypass_producer *pr= od, * @producer: pointer to producer structure * @eventfd: pointer to the eventfd context associated with the producer * - * Add the provided IRQ producer to the list of producers and connect - * with any matching token found on the IRQ consumers list. + * Add the provided IRQ producer to the set of producers and connect with = the + * consumer with a matching token, if one exists. */ int irq_bypass_register_producer(struct irq_bypass_producer *producer, struct eventfd_ctx *eventfd) { - struct irq_bypass_producer *tmp; + unsigned long token =3D (unsigned long)eventfd; struct irq_bypass_consumer *consumer; int ret; =20 @@ -101,22 +101,20 @@ int irq_bypass_register_producer(struct irq_bypass_pr= oducer *producer, =20 guard(mutex)(&lock); =20 - list_for_each_entry(tmp, &producers, node) { - if (tmp->token =3D=3D eventfd) - return -EBUSY; - } + ret =3D xa_insert(&producers, token, producer, GFP_KERNEL); + if (ret) + return ret; =20 - list_for_each_entry(consumer, &consumers, node) { - if (consumer->token =3D=3D eventfd) { - ret =3D __connect(producer, consumer); - if (ret) - return ret; - break; + consumer =3D xa_load(&consumers, token); + if (consumer) { + ret =3D __connect(producer, consumer); + if (ret) { + WARN_ON_ONCE(xa_erase(&producers, token) !=3D producer); + return ret; } } =20 producer->token =3D eventfd; - list_add(&producer->node, &producers); return 0; } EXPORT_SYMBOL_GPL(irq_bypass_register_producer); @@ -125,8 +123,9 @@ EXPORT_SYMBOL_GPL(irq_bypass_register_producer); * irq_bypass_unregister_producer - unregister IRQ bypass producer * @producer: pointer to producer structure * - * Remove a previously registered IRQ producer from the list of producers - * and disconnect it from any connected IRQ consumer. + * Remove a previously registered IRQ producer (note, it's safe to call th= is + * even if registration was unsuccessful). Disconnect from the associated + * consumer, if one exists. */ void irq_bypass_unregister_producer(struct irq_bypass_producer *producer) { @@ -138,8 +137,8 @@ void irq_bypass_unregister_producer(struct irq_bypass_p= roducer *producer) if (producer->consumer) __disconnect(producer, producer->consumer); =20 + WARN_ON_ONCE(xa_erase(&producers, (unsigned long)producer->token) !=3D pr= oducer); producer->token =3D NULL; - list_del(&producer->node); } EXPORT_SYMBOL_GPL(irq_bypass_unregister_producer); =20 @@ -148,11 +147,13 @@ EXPORT_SYMBOL_GPL(irq_bypass_unregister_producer); * @consumer: pointer to consumer structure * @eventfd: pointer to the eventfd context associated with the consumer * + * Add the provided IRQ consumer to the set of consumer and connect with t= he + * producer with a matching token, if one exists. */ int irq_bypass_register_consumer(struct irq_bypass_consumer *consumer, struct eventfd_ctx *eventfd) { - struct irq_bypass_consumer *tmp; + unsigned long token =3D (unsigned long)eventfd; struct irq_bypass_producer *producer; int ret; =20 @@ -164,22 +165,20 @@ int irq_bypass_register_consumer(struct irq_bypass_co= nsumer *consumer, =20 guard(mutex)(&lock); =20 - list_for_each_entry(tmp, &consumers, node) { - if (tmp->token =3D=3D eventfd || tmp =3D=3D consumer) - return -EBUSY; - } + ret =3D xa_insert(&consumers, token, consumer, GFP_KERNEL); + if (ret) + return ret; =20 - list_for_each_entry(producer, &producers, node) { - if (producer->token =3D=3D eventfd) { - ret =3D __connect(producer, consumer); - if (ret) - return ret; - break; + producer =3D xa_load(&producers, token); + if (producer) { + ret =3D __connect(producer, consumer); + if (ret) { + WARN_ON_ONCE(xa_erase(&consumers, token) !=3D consumer); + return ret; } } =20 consumer->token =3D eventfd; - list_add(&consumer->node, &consumers); return 0; } EXPORT_SYMBOL_GPL(irq_bypass_register_consumer); @@ -188,8 +187,9 @@ EXPORT_SYMBOL_GPL(irq_bypass_register_consumer); * irq_bypass_unregister_consumer - unregister IRQ bypass consumer * @consumer: pointer to consumer structure * - * Remove a previously registered IRQ consumer from the list of consumers - * and disconnect it from any connected IRQ producer. + * Remove a previously registered IRQ consumer (note, it's safe to call th= is + * even if registration was unsuccessful). Disconnect from the associated + * producer, if one exists. */ void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer) { @@ -201,7 +201,7 @@ void irq_bypass_unregister_consumer(struct irq_bypass_c= onsumer *consumer) if (consumer->producer) __disconnect(consumer->producer, consumer); =20 + WARN_ON_ONCE(xa_erase(&consumers, (unsigned long)consumer->token) !=3D co= nsumer); consumer->token =3D NULL; - list_del(&consumer->node); } EXPORT_SYMBOL_GPL(irq_bypass_unregister_consumer); --=20 2.49.0.504.g3bcea36a83-goog