1 /* 2 * An extensible bitmap is a bitmap that supports an 3 * arbitrary number of bits. Extensible bitmaps are 4 * used to represent sets of values, such as types, 5 * roles, categories, and classes. 6 * 7 * Each extensible bitmap is implemented as a linked 8 * list of bitmap nodes, where each bitmap node has 9 * an explicitly specified starting bit position within 10 * the total bitmap. 11 * 12 * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 13 */ 14 #ifndef _SS_EBITMAP_H_ 15 #define _SS_EBITMAP_H_ 16 17 #include <net/netlabel.h> 18 19 #ifdef CONFIG_64BIT 20 #define EBITMAP_NODE_SIZE 64 21 #else 22 #define EBITMAP_NODE_SIZE 32 23 #endif 24 25 #define EBITMAP_UNIT_NUMS ((EBITMAP_NODE_SIZE-sizeof(void *)-sizeof(u32))\ 26 / sizeof(unsigned long)) 27 #define EBITMAP_UNIT_SIZE BITS_PER_LONG 28 #define EBITMAP_SIZE (EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE) 29 #define EBITMAP_BIT 1ULL 30 #define EBITMAP_SHIFT_UNIT_SIZE(x) \ 31 (((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2) 32 33 struct ebitmap_node { 34 struct ebitmap_node *next; 35 unsigned long maps[EBITMAP_UNIT_NUMS]; 36 u32 startbit; 37 }; 38 39 struct ebitmap { 40 struct ebitmap_node *node; /* first node in the bitmap */ 41 u32 highbit; /* highest position in the total bitmap */ 42 }; 43 44 #define ebitmap_length(e) ((e)->highbit) 45 46 static inline unsigned int ebitmap_start_positive(struct ebitmap *e, 47 struct ebitmap_node **n) 48 { 49 unsigned int ofs; 50 51 for (*n = e->node; *n; *n = (*n)->next) { 52 ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); 53 if (ofs < EBITMAP_SIZE) 54 return (*n)->startbit + ofs; 55 } 56 return ebitmap_length(e); 57 } 58 59 static inline void ebitmap_init(struct ebitmap *e) 60 { 61 memset(e, 0, sizeof(*e)); 62 } 63 64 static inline unsigned int ebitmap_next_positive(struct ebitmap *e, 65 struct ebitmap_node **n, 66 unsigned int bit) 67 { 68 unsigned int ofs; 69 70 ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1); 71 if (ofs < EBITMAP_SIZE) 72 return ofs + (*n)->startbit; 73 74 for (*n = (*n)->next; *n; *n = (*n)->next) { 75 ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); 76 if (ofs < EBITMAP_SIZE) 77 return ofs + (*n)->startbit; 78 } 79 return ebitmap_length(e); 80 } 81 82 #define EBITMAP_NODE_INDEX(node, bit) \ 83 (((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE) 84 #define EBITMAP_NODE_OFFSET(node, bit) \ 85 (((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE) 86 87 static inline int ebitmap_node_get_bit(struct ebitmap_node *n, 88 unsigned int bit) 89 { 90 unsigned int index = EBITMAP_NODE_INDEX(n, bit); 91 unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 92 93 BUG_ON(index >= EBITMAP_UNIT_NUMS); 94 if ((n->maps[index] & (EBITMAP_BIT << ofs))) 95 return 1; 96 return 0; 97 } 98 99 static inline void ebitmap_node_set_bit(struct ebitmap_node *n, 100 unsigned int bit) 101 { 102 unsigned int index = EBITMAP_NODE_INDEX(n, bit); 103 unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 104 105 BUG_ON(index >= EBITMAP_UNIT_NUMS); 106 n->maps[index] |= (EBITMAP_BIT << ofs); 107 } 108 109 static inline void ebitmap_node_clr_bit(struct ebitmap_node *n, 110 unsigned int bit) 111 { 112 unsigned int index = EBITMAP_NODE_INDEX(n, bit); 113 unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 114 115 BUG_ON(index >= EBITMAP_UNIT_NUMS); 116 n->maps[index] &= ~(EBITMAP_BIT << ofs); 117 } 118 119 #define ebitmap_for_each_positive_bit(e, n, bit) \ 120 for (bit = ebitmap_start_positive(e, &n); \ 121 bit < ebitmap_length(e); \ 122 bit = ebitmap_next_positive(e, &n, bit)) \ 123 124 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2); 125 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src); 126 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit); 127 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit); 128 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value); 129 void ebitmap_destroy(struct ebitmap *e); 130 int ebitmap_read(struct ebitmap *e, void *fp); 131 int ebitmap_write(struct ebitmap *e, void *fp); 132 133 #ifdef CONFIG_NETLABEL 134 int ebitmap_netlbl_export(struct ebitmap *ebmap, 135 struct netlbl_lsm_catmap **catmap); 136 int ebitmap_netlbl_import(struct ebitmap *ebmap, 137 struct netlbl_lsm_catmap *catmap); 138 #else 139 static inline int ebitmap_netlbl_export(struct ebitmap *ebmap, 140 struct netlbl_lsm_catmap **catmap) 141 { 142 return -ENOMEM; 143 } 144 static inline int ebitmap_netlbl_import(struct ebitmap *ebmap, 145 struct netlbl_lsm_catmap *catmap) 146 { 147 return -ENOMEM; 148 } 149 #endif 150 151 #endif /* _SS_EBITMAP_H_ */ 152