Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 17 | #include <net/netlabel.h> |
| 18 | |
Waiman Long | a767f68 | 2013-07-23 17:38:41 -0400 | [diff] [blame] | 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))\ |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 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 |
KaiGai Kohei | 087feb9 | 2007-10-03 23:42:56 +0900 | [diff] [blame] | 30 | #define EBITMAP_SHIFT_UNIT_SIZE(x) \ |
| 31 | (((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 32 | |
| 33 | struct ebitmap_node { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 34 | struct ebitmap_node *next; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 35 | unsigned long maps[EBITMAP_UNIT_NUMS]; |
| 36 | u32 startbit; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 45 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 46 | static inline unsigned int ebitmap_start_positive(struct ebitmap *e, |
| 47 | struct ebitmap_node **n) |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 48 | { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 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); |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 57 | } |
| 58 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 59 | static inline void ebitmap_init(struct ebitmap *e) |
| 60 | { |
| 61 | memset(e, 0, sizeof(*e)); |
| 62 | } |
| 63 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 64 | static inline unsigned int ebitmap_next_positive(struct ebitmap *e, |
| 65 | struct ebitmap_node **n, |
| 66 | unsigned int bit) |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 67 | { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 68 | unsigned int ofs; |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 69 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 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); |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 80 | } |
| 81 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 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, |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 88 | unsigned int bit) |
| 89 | { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 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))) |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 95 | return 1; |
| 96 | return 0; |
| 97 | } |
| 98 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 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)) \ |
Stephen Smalley | 782ebb9 | 2005-09-03 15:55:16 -0700 | [diff] [blame] | 123 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 124 | int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2); |
| 125 | int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src); |
Waiman Long | fee7114 | 2013-07-23 17:38:41 -0400 | [diff] [blame] | 126 | int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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); |
Eric Paris | cee74f4 | 2010-10-13 17:50:25 -0400 | [diff] [blame] | 131 | int ebitmap_write(struct ebitmap *e, void *fp); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 132 | |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 133 | #ifdef CONFIG_NETLABEL |
| 134 | int ebitmap_netlbl_export(struct ebitmap *ebmap, |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 135 | struct netlbl_lsm_catmap **catmap); |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 136 | int ebitmap_netlbl_import(struct ebitmap *ebmap, |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 137 | struct netlbl_lsm_catmap *catmap); |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 138 | #else |
| 139 | static inline int ebitmap_netlbl_export(struct ebitmap *ebmap, |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 140 | struct netlbl_lsm_catmap **catmap) |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 141 | { |
| 142 | return -ENOMEM; |
| 143 | } |
| 144 | static inline int ebitmap_netlbl_import(struct ebitmap *ebmap, |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 145 | struct netlbl_lsm_catmap *catmap) |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 146 | { |
| 147 | return -ENOMEM; |
| 148 | } |
| 149 | #endif |
| 150 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 151 | #endif /* _SS_EBITMAP_H_ */ |