From nobody Fri Feb 13 15:41:11 2026 Received: from mail-yw1-f202.google.com (mail-yw1-f202.google.com [209.85.128.202]) (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 6B657364AE for ; Wed, 17 Apr 2024 19:15:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1713381322; cv=none; b=bK4mr7aMQcGfhdbEU41zQdvoZ/mzr8Q70rXJQusn/AapelKk6mXD8HEp7Hxjg58bidZRYdBfo2WG2F8j8tj8o7QRSmz1tKxD1EhphaZy9IojJPtZCfN6iSplcfyVh87uJpxFMpl5c26u+33+HyAZ11s16MNPPMNBtbGaYodBEGU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1713381322; c=relaxed/simple; bh=XDRUCy/tblmy0O5EO2E0OEsZFi4P01wqWmDopqbyHAE=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=rE1UZDmHPGX2bmENgSubHZEbC2spknPpZHtgdpIjtIaPdO96QLulvBvNfVsUYbSOZWrO2BYQlM/M4AqtvI2z9bE9oSVbt9y4+1++0a0rRld4XwYx0tESY8TMEdodvbapVtR9BDet7YXmz1k8Hft4Id8FFfyOKc0Ke5T5+RBMDCU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--cmllamas.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=vIZHqRuU; arc=none smtp.client-ip=209.85.128.202 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--cmllamas.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="vIZHqRuU" Received: by mail-yw1-f202.google.com with SMTP id 00721157ae682-615372710c4so322997b3.1 for ; Wed, 17 Apr 2024 12:15:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1713381319; x=1713986119; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=mgzviX8tertEbO58FSXLy5axm5X38SqIZ9fho1sI7Is=; b=vIZHqRuU9xNT6QPG8WrveBugqzL15nIhIQUTFe5z82/K81q38ivU6wbt6SZtw37wWf 8SkGd4S/11c0Af7WeQDj5VScY/r4EAVeNU+791aQhFJkegVA1Xf6d5u3AR1xe0943IBg VZu7HZyxg4jJNmXLCxHCZ3vtScQn4oVArZ3NIvXK5bpHK7i2UMQZ9E0mRMK3UORrR9xU 2cxX3zdaY6HzPZuw3+znfibp/DLuwHFC0goDn+rBWu0o0gGsxgftLDxcWmrzg12n0PkL IWU1l8yyVLuGsMvDEWA3d5UfOJ9bGvTRhfZ37mabiFjpZg4gp/PJwvNlLDeMFmYdxlQz c+fA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713381319; x=1713986119; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=mgzviX8tertEbO58FSXLy5axm5X38SqIZ9fho1sI7Is=; b=OMf+/kK0ItG4Hm+lnW+zCawKfgcjNOVxDT0HgsMNzq0mnDOndy1Av3si+nT/andvXz DFRAqMckKVc60KEKF/7dF3JlDbo9ExbKGzOqIrtRwPUQKeT/QPD3P/SCUfeJEBs0Z+E7 EHPM9+fk3ovVmq/Prl06JptuFOsaveojw47+w3F+q23uSCHU7geKpPvM9O4Cj3B9N51x 6kN+YaDbZdh+I5E/9QC3fiSoYLSGifZOfd6WKT7CbbrdxZ7xZscTSvwFq0F8NjfSwYBN VR40TfNBCknqpOcMoM48LnN2b+wvwvnQZ9WaGeenoJxropayyfihar1kUgWdD3tA5iMh BP5Q== X-Gm-Message-State: AOJu0YyjDTNWm5Gba9Om1r7jHuc/D8sdXoTA6Lu7sTh8LqyW7Fuc72ij zMJVbbk/QtKJkZ5MjCF3QQN+XtpLkiPUrcp02OKWaw6tV1a7zm9dTTI8MPFu73WuV30oF4ROoNc c8DT1uZK+vg== X-Google-Smtp-Source: AGHT+IH48BhlnuGsixBDdQqgsIeKhJr8qbkwL4npU8TNJdkUNG+s71onx1n6kkhZfSloJbxdb2GnbZHlgExmFw== X-Received: from xllamas.c.googlers.com ([fda3:e722:ac3:cc00:7f:e700:c0a8:5070]) (user=cmllamas job=sendgmr) by 2002:a0d:d94d:0:b0:618:8e4b:f4b0 with SMTP id b74-20020a0dd94d000000b006188e4bf4b0mr27664ywe.9.1713381319484; Wed, 17 Apr 2024 12:15:19 -0700 (PDT) Date: Wed, 17 Apr 2024 19:13:43 +0000 In-Reply-To: <20240417191418.1341988-1-cmllamas@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240417191418.1341988-1-cmllamas@google.com> X-Mailer: git-send-email 2.44.0.683.g7961c838ac-goog Message-ID: <20240417191418.1341988-4-cmllamas@google.com> Subject: [PATCH 3/4] binder: add support for PF_LARGE_HANDLES From: Carlos Llamas To: Greg Kroah-Hartman , "=?UTF-8?q?Arve=20Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Alice Ryhl Cc: linux-kernel@vger.kernel.org, kernel-team@android.com, Tim Murray Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce the PF_LARGE_HANDLES flag to enable the use of monotonically increasing counters to generate handles. This improves performance in transactions when dealing with a large number of references. The legacy logic performs an inorder traversal of an rbtree to find the smallest unused handle. This limitation is due to userspace using the handles as indexes (e.g. in vectors). The new logic scales much better but requires userspace to support large handle numbers. The benchmark below with 100,000 references shows the performance gains in binder_get_ref_for_node_olocked() calls with PF_LARGE_HANDLES. [ 167.855945] binder_get_ref_for_node_olocked: 17us (flag on) [ 237.088072] binder_get_ref_for_node_olocked: 18178us (flag off) Suggested-by: Tim Murray Suggested-by: Alice Ryhl Signed-off-by: Carlos Llamas Reviewed-by: Alice Ryhl --- drivers/android/binder.c | 44 ++++++++++++++++++++++------- drivers/android/binder_internal.h | 3 ++ include/uapi/linux/android/binder.h | 3 +- 3 files changed, 39 insertions(+), 11 deletions(-) diff --git a/drivers/android/binder.c b/drivers/android/binder.c index 54d27dbf1de2..f120a24c9ae6 100644 --- a/drivers/android/binder.c +++ b/drivers/android/binder.c @@ -1045,6 +1045,35 @@ static struct binder_ref *binder_get_ref_olocked(str= uct binder_proc *proc, return NULL; } =20 +static u32 next_ref_desc(struct binder_proc *proc, struct binder_node *nod= e) +{ + struct binder_ref *ref; + struct rb_node *n; + u32 desc; + + /* Handle 0 is reserved for context manager refs */ + if (node =3D=3D proc->context->binder_context_mgr_node) + return 0; + + /* Get the next handle (non-zero) */ + if (proc->flags & PF_LARGE_HANDLES) + return proc->next_ref_desc++ ? : proc->next_ref_desc++; + + /* + * Userspace doesn't support large handles. Find the smallest + * unused descriptor by doing an in-order traversal (slow). + */ + desc =3D 1; + for (n =3D rb_first(&proc->refs_by_desc); n; n =3D rb_next(n)) { + ref =3D rb_entry(n, struct binder_ref, rb_node_desc); + if (ref->data.desc > desc) + break; + desc =3D ref->data.desc + 1; + } + + return desc; +} + /** * binder_get_ref_for_node_olocked() - get the ref associated with given n= ode * @proc: binder_proc that owns the ref @@ -1068,11 +1097,9 @@ static struct binder_ref *binder_get_ref_for_node_ol= ocked( struct binder_node *node, struct binder_ref *new_ref) { - struct binder_context *context =3D proc->context; struct rb_node **p =3D &proc->refs_by_node.rb_node; struct rb_node *parent =3D NULL; struct binder_ref *ref; - struct rb_node *n; =20 while (*p) { parent =3D *p; @@ -1095,14 +1122,8 @@ static struct binder_ref *binder_get_ref_for_node_ol= ocked( rb_link_node(&new_ref->rb_node_node, parent, p); rb_insert_color(&new_ref->rb_node_node, &proc->refs_by_node); =20 - new_ref->data.desc =3D (node =3D=3D context->binder_context_mgr_node) ? 0= : 1; - for (n =3D rb_first(&proc->refs_by_desc); n !=3D NULL; n =3D rb_next(n)) { - ref =3D rb_entry(n, struct binder_ref, rb_node_desc); - if (ref->data.desc > new_ref->data.desc) - break; - new_ref->data.desc =3D ref->data.desc + 1; - } - +retry: + new_ref->data.desc =3D next_ref_desc(proc, node); p =3D &proc->refs_by_desc.rb_node; while (*p) { parent =3D *p; @@ -1112,6 +1133,8 @@ static struct binder_ref *binder_get_ref_for_node_olo= cked( p =3D &(*p)->rb_left; else if (new_ref->data.desc > ref->data.desc) p =3D &(*p)->rb_right; + else if (proc->flags & PF_LARGE_HANDLES) + goto retry; else BUG(); } @@ -5663,6 +5686,7 @@ static int binder_open(struct inode *nodp, struct fil= e *filp) get_task_struct(current->group_leader); proc->tsk =3D current->group_leader; proc->cred =3D get_cred(filp->f_cred); + proc->next_ref_desc =3D 1; INIT_LIST_HEAD(&proc->todo); init_waitqueue_head(&proc->freeze_wait); proc->default_priority =3D task_nice(current); diff --git a/drivers/android/binder_internal.h b/drivers/android/binder_int= ernal.h index 3312fe93a306..221ab7a6384a 100644 --- a/drivers/android/binder_internal.h +++ b/drivers/android/binder_internal.h @@ -337,6 +337,8 @@ struct binder_ref { * (protected by @outer_lock) * @refs_by_node: rbtree of refs ordered by ref->node * (protected by @outer_lock) + * @next_ref_desc: monotonic wrap-around counter to get the next ha= ndle + * (protected by @outer_lock) * @waiting_threads: threads currently waiting for proc work * (protected by @inner_lock) * @pid PID of group_leader of process @@ -407,6 +409,7 @@ struct binder_proc { struct rb_root nodes; struct rb_root refs_by_desc; struct rb_root refs_by_node; + u32 next_ref_desc; struct list_head waiting_threads; int pid; struct task_struct *tsk; diff --git a/include/uapi/linux/android/binder.h b/include/uapi/linux/andro= id/binder.h index 972f402415c2..d257ab8689ce 100644 --- a/include/uapi/linux/android/binder.h +++ b/include/uapi/linux/android/binder.h @@ -254,8 +254,9 @@ struct binder_extended_error { /* Used with BINDER_SET_PROC_FLAGS ioctl */ enum proc_flags { PF_SPAM_DETECTION =3D (1 << 0), /* enable oneway spam detection */ + PF_LARGE_HANDLES =3D (1 << 1), /* use large reference handles */ =20 - PF_SUPPORTED_FLAGS_MASK =3D PF_SPAM_DETECTION, + PF_SUPPORTED_FLAGS_MASK =3D (PF_SPAM_DETECTION | PF_LARGE_HANDLES), }; =20 enum { --=20 2.44.0.683.g7961c838ac-goog