Yanyg - SAN Software Engineer

LINUX IDR/IDA算法分析

目录

1 介绍

IDR/IDA用做唯一ID的分配管理。内部使用Bit实现,在内存占用和性能之间有比较好的 平衡。IDR/IDA内部使用RADIX实现。

idr.h: Small id to pointer translation service avoiding fixed sized tables.

A common problem to solve is allocating identifiers (IDs); generally small numbers which identify a thing. Examples include file descriptors, process IDs, packet identifiers in networking protocols, SCSI tags and device instance numbers. The IDR and the IDA provide a reasonable solution to the problem to avoid everybody inventing their own. The IDR provides the ability to map an ID to a pointer, while the IDA provides only ID allocation, and as a result is much more memory-efficient.

2 使用示例

2.1 loop

loop是最简单的使用。以loop.c使用为例阐述:

2.1.1 静态初始化

  /*- idr.h -*/
/* Set the IDR flag and the IDR_FREE tag */
#define IDR_RT_MARKER   (ROOT_IS_IDR | (__force gfp_t)                  \
                                        (1 << (ROOT_TAG_SHIFT + IDR_FREE)))

#define IDR_INIT_BASE(name, base) {                                     \
        .idr_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER),                 \
        .idr_base = (base),                                             \
        .idr_next = 0,                                                  \
}

/**
 * IDR_INIT() - Initialise an IDR.
 * @name: Name of IDR.
 *
 * A freshly-initialised IDR contains no IDs.
 */
#define IDR_INIT(name)  IDR_INIT_BASE(name, 0)

/**
 * DEFINE_IDR() - Define a statically-allocated IDR.
 * @name: Name of IDR.
 *
 * An IDR defined using this macro is ready for use with no additional
 * initialisation required.  It contains no IDs.
 */
#define DEFINE_IDR(name)        struct idr name = IDR_INIT(name)

  /*- loop.c -*/
  static DEFINE_IDR(loop_index_idr);

2.2 loop示例

3 References

LWN A simplified IDR API
https://lwn.net/Articles/536293/