1 #pragma GCC push_options 2 #pragma GCC optimize("O1") 3 4 #include <common/errno.h> 5 #include <common/spinlock.h> 6 7 #if ARCH(I386) || ARCH(X86_64) 8 #include <arch/x86_64/math/bitcount.h> 9 #else 10 #error Arch not supported. 11 #endif 12 13 14 /** 15 * idr: 基于radix-tree的ID-pointer的数据结构 16 * 主要功能: 17 * 1. 获取一个ID, 并且将该ID与一个指针绑定 - 需要外部加锁 18 * 2. 删除一个已分配的ID - 需要外部加锁 19 * 3. 根据ID查找对应的指针 (读操作,看情况加锁) 20 * 4. 根据ID使用新的ptr替换旧的ptr - 需要外部加锁 21 * 22 * 附加功能: 23 * 1. 给定starting_id, 查询下一个已分配的next_id (即:next_id>starting_id) 24 * 2. 销毁整个idr 25 * 26 * 27 * .... 待实现 28 */ 29 30 // 默认64位机器 31 #define IDR_BITS 6 32 #define IDR_FULL 0xfffffffffffffffful 33 34 // size = 64 35 #define IDR_SIZE (1 << IDR_BITS) 36 #define IDR_MASK ((1 << IDR_BITS) - 1) 37 38 // 能管理的ID范围[0:1<<31] 39 #define MAX_ID_SHIFT (sizeof(int) * 8 - 1) 40 #define MAX_ID_BIT (1U << MAX_ID_SHIFT) 41 #define MAX_ID_MASK (MAX_ID_BIT - 1) 42 43 // IDR可能最大的层次 以及 IDR预分配空间的最大限制 44 #define MAX_LEVEL ((MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS) 45 #define IDR_FREE_MAX (MAX_LEVEL << 1) 46 47 // 给定layer, 计算完全64叉树的大小 48 #define TREE_SIZE(layer) ((layer >= 0) ? (1ull << ((layer + 1) * IDR_BITS)) : 1) 49 50 // 计算最后(最低位)一个1的位置 (注意使用64位的版本) 51 #define __lowbit_id(x) ((x) ? (__ctzll(x)) : -1) 52 53 // 计算最前(最高位)一个1的位置 (注意使用64位的版本) 54 #define __mostbit_id(x) ((x) ? (63 - __clzll(x)) : -1) 55 56 // radix-tree 节点定义 57 struct idr_layer 58 { 59 struct idr_layer *ary[IDR_SIZE]; // IDR_SIZE叉树 60 unsigned long bitmap; // 每一位表示这个子树是否被使用 61 unsigned long full; // 64个儿子子树, 每一位代表一个子树是否满了 62 int layer; // 层数(从底向上) 63 }; 64 65 // idr: 将id与pointer绑定的数据结构 66 struct idr 67 { 68 struct idr_layer *top; 69 struct idr_layer *free_list; 70 int id_free_cnt; 71 spinlock_t lock; 72 }__attribute__((aligned(8))); 73 74 #define DECLARE_IDR(name) \ 75 struct idr name = {0}; \ 76 idr_init(&(name)); 77 78 #define DECLARE_IDR_LAYER(name) \ 79 struct idr_layer name = {0}; \ 80 memset(name, 0, sizeof(struct idr_layer)); 81 82 /** 83 * 对外函数声明 84 **/ 85 int idr_preload(struct idr *idp, gfp_t gfp_mask); 86 int idr_alloc(struct idr *idp, void *ptr, int *id); 87 void *idr_remove(struct idr *idp, int id); 88 void idr_remove_all(struct idr *idp); 89 void idr_destroy(struct idr *idp); 90 void *idr_find(struct idr *idp, int id); 91 void *idr_find_next(struct idr *idp, int start_id); 92 void *idr_find_next_getid(struct idr *idp, int64_t start_id, int *nextid); 93 int idr_replace_get_old(struct idr *idp, void *ptr, int id, void **oldptr); 94 int idr_replace(struct idr *idp, void *ptr, int id); 95 void idr_init(struct idr *idp); 96 bool idr_empty(struct idr *idp); 97 bool idr_count(struct idr *idp, int id); 98 99 /** 100 * 对外宏：遍历idr两种方式： 101 * 1. 从第一个元素开始遍历 102 * 2. 从某一个id开始遍历 103 */ 104 105 /** 106 * @brief 第一种遍历方式: 从第一个元素开始遍历 107 * @param idp idr指针 108 * @param id 遍历的id，你不需要初始化这个id，因为它每一次都是从最小已分配的id开始遍历 109 * @param ptr 数据指针(entry)，你不需要初始化这个指针 110 */ 111 #define for_each_idr_entry(idp, id, ptr) \ 112 for (id = -1, ptr = idr_find_next_getid(idp, id, &id); ptr != NULL || !idr_count(idp, id); ptr = idr_find_next_getid(idp, id, &id)) 113 114 /** 115 * @brief 第二种遍历方式: 从某一个id开始遍历 116 * @param idp idr指针 117 * @param id 遍历的id，你需要初始化这个id(请你设置为你要从哪一个id开始遍历，遍历过程将会包括这个id) 118 * @param ptr 数据指针(entry)，你不需要初始化这个指针 119 */ 120 #define for_each_idr_entry_continue(idp, id, ptr) \ 121 for (ptr = idr_find_next_getid(idp, id - 1, &id); ptr != NULL || !idr_count(idp, id); ptr = idr_find_next_getid(idp, id, &id)) 122 123 /** 124 * ida: 基于IDR实现的ID分配器 125 * 主要功能: 126 * 1. 获取一个未分配的ID 127 * 2. 询问一个ID是否被分配 128 * 3. 删除一个已分配ID 129 * 130 * 附加功能: 131 * 1. 暂定 132 */ 133 134 // 一个块的大小 - 即 sizeof(struct ida_bitmap) 135 #define IDA_CHUNK_SIZE 128 136 // ida_bitmap的长度 137 #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1) 138 // 对应linux的IDA_BITMAP_BITS = 960 = 15 * 64 139 #define IDA_FULL (IDA_BITMAP_LONGS * sizeof(long) * 8) 140 #define IDA_BITMAP_BITS IDA_FULL 141 #define IDA_BMP_SIZE (8 * sizeof(long)) 142 143 // 自定义bitmap 144 struct ida_bitmap 145 { 146 unsigned long count; // bitmap中已经分配的id数量 147 unsigned long bitmap[IDA_BITMAP_LONGS]; // bitmap本身, 每一个bit代表一个ID 148 }; 149 150 // id-allocater 管理+分配ID的数据结构 151 struct ida 152 { 153 struct idr idr; 154 struct ida_bitmap *free_list; // 预分配的数据块 155 }; 156 157 #define DECLARE_IDA(name) \ 158 struct ida name = {0}; \ 159 idr_init(&name.idr); \ 160 name.free_list = (NULL); 161 162 /** 163 * 对外函数声明 164 */ 165 void ida_init(struct ida *ida_p); 166 bool ida_empty(struct ida *ida_p); 167 int ida_preload(struct ida *ida_p, gfp_t gfp_mask); 168 int ida_alloc(struct ida *ida_p, int *p_id); 169 bool ida_count(struct ida *ida_p, int id); 170 void ida_remove(struct ida *ida_p, int id); 171 void ida_destroy(struct ida *ida_p); 172 173 #pragma GCC pop_options