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