From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f47.google.com (mail-wr1-f47.google.com [209.85.221.47]) (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 4780F19F461 for ; Tue, 20 May 2025 12:43:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.47 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747744987; cv=none; b=VlrPox/R+x4bOW8uWWUcAK7XQrn7On+7t4nfaGzHDampAIsdpE6K4SbIF938iACtJmu2VmcsfiqSkJeUBvzlc95uDdRO9QYvsAkCNK05qUpeKzsV0LDhUb13hM3Z7i+PCZ5G94Y2KL1fIrbbeFeMVjhwkcWaQKNkr32zJ/82Kx4= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747744987; c=relaxed/simple; bh=EAHzzRlqwHD0tyyHiLnOawAa1WH6/3DVglP+aReQHPc=; h=MIME-Version:References:In-Reply-To:From:Date:Message-ID:Subject: To:Cc:Content-Type; b=Ynjb5PhEW10jVgIO7XHjwEz5/NbkbAvZiK3bZ0oyOWI4g+TTslOZRZXV9TiHiVFMTfbnbEoF1WbsIbh3xNEqzpjZ7hHOqc40ZAPQYC4YoT/iw9/46onNBbcNn0vbSijIt38jMgugFItEiI1oOgTp7GF/OFQliWN5BJrUdYvqi+I= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=B1VMsJdU; arc=none smtp.client-ip=209.85.221.47 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=google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="B1VMsJdU" Received: by mail-wr1-f47.google.com with SMTP id ffacd0b85a97d-3a366843fa6so1958461f8f.1 for ; Tue, 20 May 2025 05:43:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1747744983; x=1748349783; darn=vger.kernel.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=EAHzzRlqwHD0tyyHiLnOawAa1WH6/3DVglP+aReQHPc=; b=B1VMsJdUTtNZ5AeibbEr7PXGb+bgZA78QdWsAheDRcoVinv9wUHKmtW7183x/7R0Q7 77EZ2RqvZSAyd1Mht6XSmypEFCwYBLIbqobkXmRcFX8xPvUOGZh3Ip54AT205WhRjxzR eaQ7jG6lgIEFdQX5KmLB1Pf+hjwX1x9FD0E/0hcvkbOm/4lVfm13L+ekdVyvp4l3zgD7 Li5wKHHeOy+310BDqvSE8RjphNofrdvBrZZP1E8AojPm495mntqF+qc5p+iA7h05mJ4F vv3Iwd2Zn/cSuN959zeQ6lm9B9oZ0pSGWgudpYIRT5U59PA1KEvZXDXl5skAM1R49jQ5 XeRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747744983; x=1748349783; h=content-transfer-encoding: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=EAHzzRlqwHD0tyyHiLnOawAa1WH6/3DVglP+aReQHPc=; b=CpAqnl/h7+o4clNKOJZGWhPR/GXHk8fHIkORqIgqksUmbAI66NRoDutjV7x7lI0AVd AkzuUHRmPrLserF2tnlmX4c+wWgoCgJ0VL2Dc5TsHOkXDESasGKPTWiWji3T8rMiPOOS Z+7XmAiY790jeny787PlqgZemAYiIbjx5hAgIo6bhDREM++NhoDbG5ivRbQfagA5Bew8 xdnGFSt3OhaIHjUE5xasPkXtyl/ln3Anh1V2FCyjoesri27/xXrUyTwvWqie4XO6kP+3 3MwcU8IBOVcfqhI1QTDRw3Sn9u3m8uu5FA352MPPLJLaK+1k05jDucZZXR5xwo/wra09 wSFg== X-Forwarded-Encrypted: i=1; AJvYcCUWhCD6Axnt48lYVqRHgz8FYNq4V9ivAzUrNNPnhqzo5odjydPc9n2vlV6v4OtHEmYbnYYSuCj44rd6KMJA2w==@vger.kernel.org X-Gm-Message-State: AOJu0Yzm3XVyU2rIPHwwTOxBdNbHL0taEW/IbQTIYx1DX3saQgRlHLRX 34CCny6aTNaepqgc37CmnaBsgrG6jhXAohcy3p28giyTKMdBKGdgiJ3HzKOd0rQ2Zm73tiZTwXW /npQDk3lFLgGhHHYHoTxyQ0gfDJmqBmRZs4U2uzXZ X-Gm-Gg: ASbGnctW3pXJkaJ58zDv3JQ0TkB6XFmWCsX9RXo1qXOlW/xTZxzVE0fbcaisRzLjreC tQeg2W6BRhMJhaBK1OuttdCH0vWcT91wQ2lCHVxfQnM0hFAKohj3XQXRMVpSBoFgyUntdjxbSpF z67V7o3jvR8oV6tDXpqMWa3Y2ndTqUfCJjSvY2Nn/i+/iS X-Google-Smtp-Source: AGHT+IHS0wTiDrmTRT4pPLA0kd7EuOcSAEADiFb2xPxNv7tTT14Pcvfk2m6J1zKafjkxbkm02/1Z8djAmA08uVBrLX8= X-Received: by 2002:a05:6000:40e0:b0:3a0:b733:f264 with SMTP id ffacd0b85a97d-3a35fe5ba7amr14020745f8f.11.1747744983401; Tue, 20 May 2025 05:43:03 -0700 (PDT) Precedence: bulk X-Mailing-List: rust-for-linux@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 References: <20250519161712.2609395-1-bqe@google.com> <20250519161712.2609395-6-bqe@google.com> <682bc528.c80a0220.13f632.9ec0@mx.google.com> In-Reply-To: From: Alice Ryhl Date: Tue, 20 May 2025 05:42:51 -0700 X-Gm-Features: AX0GCFvPyNIDsyx7gzZx16RwjzE4BKj1SXehnk-VJvEazvtsPhKBabrEv6qfeaI Message-ID: Subject: Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap To: Boqun Feng Cc: Jann Horn , Burak Emir , Yury Norov , Kees Cook , Rasmus Villemoes , Viresh Kumar , Miguel Ojeda , Alex Gaynor , Gary Guo , =?UTF-8?Q?Bj=C3=B6rn_Roy_Baron?= , Benno Lossin , Andreas Hindborg , Trevor Gross , "Gustavo A . R . Silva" , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, linux-hardening@vger.kernel.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Mon, May 19, 2025 at 10:21=E2=80=AFPM Boqun Feng = wrote: > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote: > > On Mon, May 19, 2025 at 4:56=E2=80=AFPM Boqun Feng wrote: > > > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote: > > > > On Mon, May 19, 2025 at 6:20=E2=80=AFPM Burak Emir = wrote: > > > > > This is a port of the Binder data structure introduced in commit > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") = to > > > > > Rust. > > > > > > > > Stupid high-level side comment: > > > > > > > > That commit looks like it changed a simple linear rbtree scan (whic= h > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option > > > > might have been to use an augmented rbtree, reducing the O(n) rbtre= e > > > > scan to an O(log n) rbtree lookup, just like how finding a free are= a > > > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said > > > > We need the smallest ID without a value, not the smallest ID in use. > > > > Ok, but it shouldn't be hard to write a Rust function that search that, > right? My point was mostly the Rust rbtree binding can do O(log n) > search. I have no idea about "even so, should we try something like Jann > suggested". And I think your other reply basically says no. We would need to store additional data in the r/b tree to know whether to go left or right, so it would be somewhat tricky. We don't have an implementation of that in Rust. Alice