idr_destroy() would loop over the removed and alloced
RB tree nodes freeing them but not removing them from
the trees. From the perspective of the RB tree those
nodes would remain valid, while in fact, they were free
memory, potentially reallocated for other purposes, or
otherwise overwritten by the allocator with metadata.
This would cause (seemingly random) memory corruption
crashes triggered by the RB tree code trying to access
link fields from the free'd nodes.
Fix that by removing the nodes before freeing them.
Signed-off-by: George Poulios <gpoulios@census-labs.com>
Most tools used for compliance and SBOM generation use SPDX identifiers
This change brings us a step closer to an easy SBOM generation.
Signed-off-by: Alin Jerpelea <alin.jerpelea@sony.com>
This is a tool for associating discrete IDs with addresses.
This tool is implemented through the red-black tree method provided by <sys/tree.h>, and the time complexity when calling, searching, and deleting is optimized to O(logn)
The implementation is the moving node operation of two red-black trees
1. When applying for a node, it will first check whether there is an available node in the "removed" tree. If so, the memory address of the node will be reused and moved to the "alloced" tree.
2. If the "removed" tree is an "empty tree", then the node will be requested from the memory and added to the "alloced" tree
3. Similarly, when removing a node, we set the address pointed to in the node to "NULL" and move it to the "removed" tree. Next time we alloc the node, we can reduce the overhead caused by memory application
For now, we still have something that can be optimized, and that is the memory elimination mechanism of the "removed tree". The current implementation will only release all the content under the "removed" tree when the idtree is destroyed.
Signed-off-by: chenrun1 <chenrun1@xiaomi.com>
George Poulios
Alin Jerpelea
chenrun1