dbitmap.h

  1/* SPDX-License-Identifier: GPL-2.0-only */
  2/*
  3 * Copyright 2024 Google LLC
  4 *
  5 * dbitmap - dynamically sized bitmap library.
  6 *
  7 * Used by the binder driver to optimize the allocation of the smallest
  8 * available descriptor ID. Each bit in the bitmap represents the state
  9 * of an ID.
 10 *
 11 * A dbitmap can grow or shrink as needed. This part has been designed
 12 * considering that users might need to briefly release their locks in
 13 * order to allocate memory for the new bitmap. These operations then,
 14 * are verified to determine if the grow or shrink is sill valid.
 15 *
 16 * This library does not provide protection against concurrent access
 17 * by itself. Binder uses the proc->outer_lock for this purpose.
 18 */
 19
 20#ifndef _LINUX_DBITMAP_H
 21#define _LINUX_DBITMAP_H
 22#include <linux/bitmap.h>
 23
 24#define NBITS_MIN	BITS_PER_TYPE(unsigned long)
 25
 26struct dbitmap {
 27	unsigned int nbits;
 28	unsigned long *map;
 29};
 30
 31static inline int dbitmap_enabled(struct dbitmap *dmap)
 32{
 33	return !!dmap->nbits;
 34}
 35
 36static inline void dbitmap_free(struct dbitmap *dmap)
 37{
 38	dmap->nbits = 0;
 39	kfree(dmap->map);
 40	dmap->map = NULL;
 41}
 42
 43/* Returns the nbits that a dbitmap can shrink to, 0 if not possible. */
 44static inline unsigned int dbitmap_shrink_nbits(struct dbitmap *dmap)
 45{
 46	unsigned int bit;
 47
 48	if (dmap->nbits <= NBITS_MIN)
 49		return 0;
 50
 51	/*
 52	 * Determine if the bitmap can shrink based on the position of
 53	 * its last set bit. If the bit is within the first quarter of
 54	 * the bitmap then shrinking is possible. In this case, the
 55	 * bitmap should shrink to half its current size.
 56	 */
 57	bit = find_last_bit(dmap->map, dmap->nbits);
 58	if (bit < (dmap->nbits >> 2))
 59		return dmap->nbits >> 1;
 60
 61	/* find_last_bit() returns dmap->nbits when no bits are set. */
 62	if (bit == dmap->nbits)
 63		return NBITS_MIN;
 64
 65	return 0;
 66}
 67
 68/* Replace the internal bitmap with a new one of different size */
 69static inline void
 70dbitmap_replace(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
 71{
 72	bitmap_copy(new, dmap->map, min(dmap->nbits, nbits));
 73	kfree(dmap->map);
 74	dmap->map = new;
 75	dmap->nbits = nbits;
 76}
 77
 78static inline void
 79dbitmap_shrink(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
 80{
 81	if (!new)
 82		return;
 83
 84	/*
 85	 * Verify that shrinking to @nbits is still possible. The @new
 86	 * bitmap might have been allocated without locks, so this call
 87	 * could now be outdated. In this case, free @new and move on.
 88	 */
 89	if (!dbitmap_enabled(dmap) || dbitmap_shrink_nbits(dmap) != nbits) {
 90		kfree(new);
 91		return;
 92	}
 93
 94	dbitmap_replace(dmap, new, nbits);
 95}
 96
 97/* Returns the nbits that a dbitmap can grow to. */
 98static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)
 99{
100	return dmap->nbits << 1;
101}
102
103static inline void
104dbitmap_grow(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)
105{
106	/*
107	 * Verify that growing to @nbits is still possible. The @new
108	 * bitmap might have been allocated without locks, so this call
109	 * could now be outdated. In this case, free @new and move on.
110	 */
111	if (!dbitmap_enabled(dmap) || nbits <= dmap->nbits) {
112		kfree(new);
113		return;
114	}
115
116	/*
117	 * Check for ENOMEM after confirming the grow operation is still
118	 * required. This ensures we only disable the dbitmap when it's
119	 * necessary. Once the dbitmap is disabled, binder will fallback
120	 * to slow_desc_lookup_olocked().
121	 */
122	if (!new) {
123		dbitmap_free(dmap);
124		return;
125	}
126
127	dbitmap_replace(dmap, new, nbits);
128}
129
130/*
131 * Finds and sets the next zero bit in the bitmap. Upon success @bit
132 * is populated with the index and 0 is returned. Otherwise, -ENOSPC
133 * is returned to indicate that a dbitmap_grow() is needed.
134 */
135static inline int
136dbitmap_acquire_next_zero_bit(struct dbitmap *dmap, unsigned long offset,
137			      unsigned long *bit)
138{
139	unsigned long n;
140
141	n = find_next_zero_bit(dmap->map, dmap->nbits, offset);
142	if (n == dmap->nbits)
143		return -ENOSPC;
144
145	*bit = n;
146	set_bit(n, dmap->map);
147
148	return 0;
149}
150
151static inline void
152dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit)
153{
154	clear_bit(bit, dmap->map);
155}
156
157static inline int dbitmap_init(struct dbitmap *dmap)
158{
159	dmap->map = bitmap_zalloc(NBITS_MIN, GFP_KERNEL);
160	if (!dmap->map) {
161		dmap->nbits = 0;
162		return -ENOMEM;
163	}
164
165	dmap->nbits = NBITS_MIN;
166
167	return 0;
168}
169#endif