Memory and resource allocation are fundamental operations inside the Linux kernel. Whether assigning device IDs, managing CPU masks, allocating interrupt vectors, or tracking hardware resources, the kernel relies on specialized data structures optimized for different allocation patterns.

Recently, an interesting Linux Kernel Mailing List (LKML) discussion initiated by Yury Norov explored different approaches for region allocation, comparing Bitmap, IDA, and Maple Tree. Inspired by that discussion, I built a small Linux Kernel Module (LKM) to understand how Bitmap and IDA work internally and to benchmark their allocation time.

This article walks through the concepts, implementation, and practical differences between these allocators.

---

Why This Topic Matters

Kernel developers frequently face questions such as:

• Should a resource be represented as individual IDs?
• Should contiguous regions be allocated?
• Which data structure scales better as the number of resources grows?
• How much overhead does each allocator introduce?

The answer depends entirely on the allocation problem.

---

Motivation

The implementation was inspired by the following LKML discussion:

Message-ID

20260717053241.916441-1-ynorov@nvidia.com

The discussion compares several allocation mechanisms for variable-sized regions, including:

• Bitmap
• IDA
• Maple Tree

Although this module implements only Bitmap and IDA, understanding these two allocators provides an excellent foundation before exploring Maple Tree.

---

Understanding Bitmap Allocation

A bitmap represents every resource using a single bit.

Each bit has only two possible states:

• 0 → Free
• 1 → Allocated

When a contiguous region is required, the kernel searches for consecutive zero bits and marks them as allocated.

This approach is extremely memory efficient because one bit represents one resource.

Common Kernel APIs

bitmap_zalloc()

bitmap_find_next_zero_area()

bitmap_set()

bitmap_clear()

bitmap_free()

---

Bitmap Allocation Workflow

1. Allocate bitmap memory.
2. Search for the next free contiguous region.
3. Mark the bits as allocated.
4. Perform work.
5. Clear the bits.
6. Free the bitmap.

---

Understanding IDA

IDA stands for Integer ID Allocator.

Unlike Bitmap, IDA does not allocate contiguous regions.

Instead, it allocates unique integer identifiers.

Typical output might be:

0
1
2
3
4
5

Each allocation is completely independent.

IDA is widely used throughout the Linux kernel whenever objects require unique identifiers.

Common Kernel APIs

ida_init()

ida_alloc()

ida_free()

ida_destroy()

---

IDA Allocation Workflow

1. Initialize IDA.
2. Allocate one integer ID.
3. Use the ID.
4. Return the ID.
5. Destroy the allocator.

---

Why Bitmap and IDA Solve Different Problems

Although both allocate resources, they are designed for different scenarios.

Bitmap focuses on contiguous regions, while IDA focuses on unique identifiers.

Examples include:

Bitmap

• CPU masks
• Memory regions
• DMA regions
• Block allocation
• Fixed resource maps

IDA

• Device numbers
• Driver IDs
• Kernel object identifiers
• Subsystem IDs

---

Linux Kernel Module Overview

The module supports three execution modes.

Mode 1

Runs only the Bitmap allocator.

sudo insmod region_demo.ko mode=1

---

Mode 2

Runs only the IDA allocator.

sudo insmod region_demo.ko mode=2

---

Mode 3

Runs both allocators for comparison.

sudo insmod region_demo.ko mode=3

---

Measuring Allocation Time

The module measures allocation latency using the kernel timing API.

start = ktime_get();

/* allocation */

end = ktime_get();

ktime_to_ns(end - start);

Although the benchmark is intentionally simple, it demonstrates how kernel operations can be measured at nanosecond resolution.

---

Example Kernel Output

Bitmap

Region allocator demo loaded

Bitmap allocated region

start=0 size=8

Bitmap alloc time 13800 ns

IDA

IDA allocated id=0

IDA allocated id=1

IDA allocated id=2

...

IDA alloc time 19200 ns

Bitmap vs IDA

Feature	Bitmap	IDA
Stores	Bits	Integer IDs
Allocation Type	Contiguous regions	Individual IDs
Memory Usage	Very low	Dynamic
Sparse Allocation	Not ideal	Excellent
Contiguous Allocation	Yes	No
Primary Use	Resource maps	Kernel object IDs
Typical Search	Bit scanning	Tree/XArray traversal

---

Where Does Maple Tree Fit?

Modern Linux kernels increasingly use Maple Tree for managing variable-sized ranges efficiently.

Compared with Bitmap and IDA, Maple Tree offers:

• Better scalability
• Efficient range management
• Reduced tree overhead
• Excellent performance for large sparse address spaces

Many newer kernel subsystems are gradually adopting Maple Tree where traditional tree-based structures were previously used.

---

Key Takeaways

• Bitmap is ideal for contiguous resource allocation.
• IDA is designed for allocating unique integer identifiers.
• Both allocators solve different problems and are widely used throughout the Linux kernel.
• Measuring allocator performance helps understand the trade-offs between different kernel data structures.
• Learning Bitmap and IDA provides an excellent foundation before exploring Maple Tree and more advanced kernel memory management techniques.

---

Conclusion

Kernel allocation is much more than simply requesting memory. Different kernel subsystems require different allocation strategies depending on whether they manage contiguous regions, sparse identifiers, or large variable-sized ranges.

This small Linux Kernel Module demonstrates how Bitmap and IDA operate internally, provides a simple timing benchmark, and connects practical experimentation with an ongoing LKML discussion. If you're learning Linux kernel development, implementing these allocators yourself is one of the best ways to understand the design decisions behind modern kernel resource management.

---

Source Code

GitHub Repository

https://github.com/aj333git/linux_kernel_bitmap_ida

---

References

• Linux Kernel Documentation
• Linux Kernel Bitmap API
• Linux Kernel IDA API
• Linux Kernel Mailing List (LKML)
• LKML Message-ID: 20260717053241.916441-1-ynorov@nvidia.com