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:
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:
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
- Allocate bitmap memory.
- Search for the next free contiguous region.
- Mark the bits as allocated.
- Perform work.
- Clear the bits.
- 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
- Initialize IDA.
- Allocate one integer ID.
- Use the ID.
- Return the ID.
- 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
