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