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 #define EBITMAP_UNIT_NUMS ((32 - sizeof(void *) - sizeof(u32)) \ 20 / sizeof(unsigned long)) 21 #define EBITMAP_UNIT_SIZE BITS_PER_LONG 22 #define EBITMAP_SIZE (EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE) 23 #define EBITMAP_BIT 1ULL 24 #define EBITMAP_SHIFT_UNIT_SIZE(x) \ 25 (((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2) 26 27 struct ebitmap_node { 28 struct ebitmap_node *next; 29 unsigned long maps[EBITMAP_UNIT_NUMS]; 30 u32 startbit; 31 }; 32 33 struct ebitmap { 34 struct ebitmap_node *node; /* first node in the bitmap */ 35 u32 highbit; /* highest position in the total bitmap */ 36 }; 37 38 #define ebitmap_length(e) ((e)->highbit) 39 40 static inline unsigned int ebitmap_start_positive(struct ebitmap *e, 41 struct ebitmap_node **n) 42 { 43 unsigned int ofs; 44 45 for (*n = e->node; *n; *n = (*n)->next) { 46 ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); 47 if (ofs < EBITMAP_SIZE) 48 return (*n)->startbit + ofs; 49 } 50 return ebitmap_length(e); 51 } 52 53 static inline void ebitmap_init(struct ebitmap *e) 54 { 55 memset(e, 0, sizeof(*e)); 56 } 57 58 static inline unsigned int ebitmap_next_positive(struct ebitmap *e, 59 struct ebitmap_node **n, 60 unsigned int bit) 61 { 62 unsigned int ofs; 63 64 ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1); 65 if (ofs < EBITMAP_SIZE) 66 return ofs + (*n)->startbit; 67 68 for (*n = (*n)->next; *n; *n = (*n)->next) { 69 ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); 70 if (ofs < EBITMAP_SIZE) 71 return ofs + (*n)->startbit; 72 } 73 return ebitmap_length(e); 74 } 75 76 #define EBITMAP_NODE_INDEX(node, bit) \ 77 (((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE) 78 #define EBITMAP_NODE_OFFSET(node, bit) \ 79 (((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE) 80 81 static inline int ebitmap_node_get_bit(struct ebitmap_node *n, 82 unsigned int bit) 83 { 84 unsigned int index = EBITMAP_NODE_INDEX(n, bit); 85 unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 86 87 BUG_ON(index >= EBITMAP_UNIT_NUMS); 88 if ((n->maps[index] & (EBITMAP_BIT << ofs))) 89 return 1; 90 return 0; 91 } 92 93 static inline void ebitmap_node_set_bit(struct ebitmap_node *n, 94 unsigned int bit) 95 { 96 unsigned int index = EBITMAP_NODE_INDEX(n, bit); 97 unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 98 99 BUG_ON(index >= EBITMAP_UNIT_NUMS); 100 n->maps[index] |= (EBITMAP_BIT << ofs); 101 } 102 103 static inline void ebitmap_node_clr_bit(struct ebitmap_node *n, 104 unsigned int bit) 105 { 106 unsigned int index = EBITMAP_NODE_INDEX(n, bit); 107 unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 108 109 BUG_ON(index >= EBITMAP_UNIT_NUMS); 110 n->maps[index] &= ~(EBITMAP_BIT << ofs); 111 } 112 113 #define ebitmap_for_each_positive_bit(e, n, bit) \ 114 for (bit = ebitmap_start_positive(e, &n); \ 115 bit < ebitmap_length(e); \ 116 bit = ebitmap_next_positive(e, &n, bit)) \ 117 118 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2); 119 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src); 120 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2); 121 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit); 122 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value); 123 void ebitmap_destroy(struct ebitmap *e); 124 int ebitmap_read(struct ebitmap *e, void *fp); 125 int ebitmap_write(struct ebitmap *e, void *fp); 126 127 #ifdef CONFIG_NETLABEL 128 int ebitmap_netlbl_export(struct ebitmap *ebmap, 129 struct netlbl_lsm_secattr_catmap **catmap); 130 int ebitmap_netlbl_import(struct ebitmap *ebmap, 131 struct netlbl_lsm_secattr_catmap *catmap); 132 #else 133 static inline int ebitmap_netlbl_export(struct ebitmap *ebmap, 134 struct netlbl_lsm_secattr_catmap **catmap) 135 { 136 return -ENOMEM; 137 } 138 static inline int ebitmap_netlbl_import(struct ebitmap *ebmap, 139 struct netlbl_lsm_secattr_catmap *catmap) 140 { 141 return -ENOMEM; 142 } 143 #endif 144 145 #endif /* _SS_EBITMAP_H_ */ 146