« Previous Lecture | Next Lecture »

Why Scanning a Bitmask Needs Dedicated APIs

A bitmap is just an array of unsigned long words where each bit represents a flag: a free CPU, a free page frame, or a ready-to-run task priority level. Several performance-critical parts of the kernel — scheduling classes like SCHED_FIFO and SCHED_RR, CPU topology masks, and memory allocators — need to answer the question “which is the first set bit in this bitmap?” thousands of times per second. Looping bit-by-bit with a shift-and-test pattern works, but it wastes cycles checking bits one at a time when hardware instructions can locate a set bit inside a whole word in a single step. The kernel’s bitmask search API exists precisely to use those hardware instructions instead of a manual loop.

The Core Search Functions

These prototypes live in include/asm-generic/bitops/find.h and are still the primary bitmap search entry points on kernel 6.x:

• unsigned long find_first_bit(const unsigned long *addr, unsigned long size); — returns the position of the first set bit in a region of size bits, or size itself if nothing is set.
• unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size); — the mirror image: returns the first cleared bit, or size if every bit is set.
• unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset); — resumes a scan after a given offset, useful when you are walking through every set bit one at a time.
• unsigned long find_next_and_bit(...) — finds the next bit set in both of two bitmaps, handy for combining a “capability” mask with an “enabled” mask.
• unsigned long find_last_bit(const unsigned long *addr, unsigned long size); — returns the position of the highest set bit.

Iterating With for_each_set_bit()

<linux/bitops.h> also defines convenience macros that wrap find_next_bit() into a clean loop, so you rarely call find_next_bit() directly in driver code:

unsigned long bit;

for_each_set_bit(bit, my_bitmap, NUM_BITS) {
	pr_info("ep_bitmap: bit %lu is set\n", bit);
}

The mirror macro for_each_clear_bit() walks the cleared bits instead, and both have a _from variant (for_each_set_bit_from()) that starts the scan at a given bit index rather than from zero.

Our Original Demo: Scanning a Device Status Bitmap

Here is an original misc-device driver, ep_bitscan_demo, built for this lecture. It maintains a small bitmap representing which of 32 hardware sub-channels currently have pending data, and uses for_each_set_bit() to report every pending channel on read.

#include <linux/module.h>
#include <linux/miscdevice.h>
#include <linux/fs.h>
#include <linux/bitops.h>
#include <linux/uaccess.h>

#define EP_NUM_CHANNELS 32

static unsigned long ep_channel_bitmap;

static ssize_t ep_scan_read(struct file *f, char __user *buf,
			     size_t count, loff_t *ppos)
{
	char line[64];
	int len = 0;
	unsigned long bit;

	if (*ppos)
		return 0;

	for_each_set_bit(bit, &ep_channel_bitmap, EP_NUM_CHANNELS) {
		len += scnprintf(line + len, sizeof(line) - len,
				  "channel %lu pending\n", bit);
	}

	if (len == 0)
		len = scnprintf(line, sizeof(line), "no channels pending\n");

	if (copy_to_user(buf, line, len))
		return -EFAULT;

	*ppos += len;
	return len;
}

static ssize_t ep_scan_write(struct file *f, const char __user *buf,
			      size_t count, loff_t *ppos)
{
	unsigned int ch;

	if (kstrtouint_from_user(buf, count, 10, &ch))
		return -EINVAL;

	if (ch >= EP_NUM_CHANNELS)
		return -EINVAL;

	set_bit(ch, &ep_channel_bitmap);
	return count;
}

static const struct file_operations ep_scan_fops = {
	.read = ep_scan_read,
	.write = ep_scan_write,
};

static struct miscdevice ep_scan_dev = {
	.minor = MISC_DYNAMIC_MINOR,
	.name = "ep_bitscan_demo",
	.fops = &ep_scan_fops,
};

static int __init ep_scan_init(void)
{
	return misc_register(&ep_scan_dev);
}

static void __exit ep_scan_exit(void)
{
	misc_deregister(&ep_scan_dev);
}

module_init(ep_scan_init);
module_exit(ep_scan_exit);
MODULE_LICENSE("GPL");

Writing a channel number to /dev/ep_bitscan_demo sets that bit; reading the device lists every currently-pending channel by walking the bitmap with for_each_set_bit() instead of a manual shift-and-test loop.

Comparison Table

Frequently Asked Questions

Q1. What happens if no bit is set when I call find_first_bit()?
It returns a value equal to the size parameter, which you should always check against before using the result as an index.

Q2. Are these functions safe to call concurrently with a writer?
No — scanning a bitmap that another CPU is modifying still needs its own protection, typically a spinlock or an RCU-friendly structure, exactly like any other shared data.

Q3. Where in the real kernel are these APIs used?
CPU affinity masks, memory allocator free-bit tracking, and priority-based scheduling classes are common consumers of the bitmap search family.

Q4. What is the difference between find_next_bit() and for_each_set_bit()?
for_each_set_bit() is a loop macro built on top of find_next_bit(); you rarely need to call find_next_bit() yourself once you use the macro.

Q5. Do these functions work on multi-word (large) bitmaps?
Yes, the size parameter is in bits, not words, so these functions transparently handle bitmaps spanning many unsigned long words.

Q6. Is there a version for finding a bit set in two bitmaps at once?
Yes, find_next_and_bit() finds the next bit set in both of two supplied bitmaps in a single scan.

Practice Exercises

1. Add a for_each_clear_bit() based ioctl that reports which channels are currently free.
2. Extend the demo to a 128-bit bitmap spanning multiple unsigned long words and confirm the API still works unchanged.
3. Replace the manual write-based bit-set with test_and_set_bit() from the previous lecture and reject duplicate sets.

« Previous Lecture | Next Lecture »