169 lines · c
1/* SPDX-License-Identifier: GPL-2.0-only */2/*3 * Copyright 2024 Google LLC4 *5 * dbitmap - dynamically sized bitmap library.6 *7 * Used by the binder driver to optimize the allocation of the smallest8 * available descriptor ID. Each bit in the bitmap represents the state9 * of an ID.10 *11 * A dbitmap can grow or shrink as needed. This part has been designed12 * considering that users might need to briefly release their locks in13 * 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 access17 * by itself. Binder uses the proc->outer_lock for this purpose.18 */19 20#ifndef _LINUX_DBITMAP_H21#define _LINUX_DBITMAP_H22#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}41 42/* Returns the nbits that a dbitmap can shrink to, 0 if not possible. */43static inline unsigned int dbitmap_shrink_nbits(struct dbitmap *dmap)44{45 unsigned int bit;46 47 if (dmap->nbits <= NBITS_MIN)48 return 0;49 50 /*51 * Determine if the bitmap can shrink based on the position of52 * its last set bit. If the bit is within the first quarter of53 * the bitmap then shrinking is possible. In this case, the54 * bitmap should shrink to half its current size.55 */56 bit = find_last_bit(dmap->map, dmap->nbits);57 if (bit < (dmap->nbits >> 2))58 return dmap->nbits >> 1;59 60 /* find_last_bit() returns dmap->nbits when no bits are set. */61 if (bit == dmap->nbits)62 return NBITS_MIN;63 64 return 0;65}66 67/* Replace the internal bitmap with a new one of different size */68static inline void69dbitmap_replace(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)70{71 bitmap_copy(new, dmap->map, min(dmap->nbits, nbits));72 kfree(dmap->map);73 dmap->map = new;74 dmap->nbits = nbits;75}76 77static inline void78dbitmap_shrink(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)79{80 if (!new)81 return;82 83 /*84 * Verify that shrinking to @nbits is still possible. The @new85 * bitmap might have been allocated without locks, so this call86 * could now be outdated. In this case, free @new and move on.87 */88 if (!dbitmap_enabled(dmap) || dbitmap_shrink_nbits(dmap) != nbits) {89 kfree(new);90 return;91 }92 93 dbitmap_replace(dmap, new, nbits);94}95 96/* Returns the nbits that a dbitmap can grow to. */97static inline unsigned int dbitmap_grow_nbits(struct dbitmap *dmap)98{99 return dmap->nbits << 1;100}101 102static inline void103dbitmap_grow(struct dbitmap *dmap, unsigned long *new, unsigned int nbits)104{105 /*106 * Verify that growing to @nbits is still possible. The @new107 * bitmap might have been allocated without locks, so this call108 * could now be outdated. In this case, free @new and move on.109 */110 if (!dbitmap_enabled(dmap) || nbits <= dmap->nbits) {111 kfree(new);112 return;113 }114 115 /*116 * Check for ENOMEM after confirming the grow operation is still117 * required. This ensures we only disable the dbitmap when it's118 * necessary. Once the dbitmap is disabled, binder will fallback119 * to slow_desc_lookup_olocked().120 */121 if (!new) {122 dbitmap_free(dmap);123 return;124 }125 126 dbitmap_replace(dmap, new, nbits);127}128 129/*130 * Finds and sets the next zero bit in the bitmap. Upon success @bit131 * is populated with the index and 0 is returned. Otherwise, -ENOSPC132 * is returned to indicate that a dbitmap_grow() is needed.133 */134static inline int135dbitmap_acquire_next_zero_bit(struct dbitmap *dmap, unsigned long offset,136 unsigned long *bit)137{138 unsigned long n;139 140 n = find_next_zero_bit(dmap->map, dmap->nbits, offset);141 if (n == dmap->nbits)142 return -ENOSPC;143 144 *bit = n;145 set_bit(n, dmap->map);146 147 return 0;148}149 150static inline void151dbitmap_clear_bit(struct dbitmap *dmap, unsigned long bit)152{153 clear_bit(bit, dmap->map);154}155 156static inline int dbitmap_init(struct dbitmap *dmap)157{158 dmap->map = bitmap_zalloc(NBITS_MIN, GFP_KERNEL);159 if (!dmap->map) {160 dmap->nbits = 0;161 return -ENOMEM;162 }163 164 dmap->nbits = NBITS_MIN;165 166 return 0;167}168#endif169