selinux/ss/ebitmap.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /*
0003  * An extensible bitmap is a bitmap that supports an
0004  * arbitrary number of bits.  Extensible bitmaps are
0005  * used to represent sets of values, such as types,
0006  * roles, categories, and classes.
0007  *
0008  * Each extensible bitmap is implemented as a linked
0009  * list of bitmap nodes, where each bitmap node has
0010  * an explicitly specified starting bit position within
0011  * the total bitmap.
0012  *
0013  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
0014  */
0015 #ifndef _SS_EBITMAP_H_
0016 #define _SS_EBITMAP_H_
0017
0018 #include <net/netlabel.h>
0019
0020 #ifdef CONFIG_64BIT
0021 #define EBITMAP_NODE_SIZE   64
0022 #else
0023 #define EBITMAP_NODE_SIZE   32
0024 #endif
0025
0026 #define EBITMAP_UNIT_NUMS   ((EBITMAP_NODE_SIZE-sizeof(void *)-sizeof(u32))\
0027                     / sizeof(unsigned long))
0028 #define EBITMAP_UNIT_SIZE   BITS_PER_LONG
0029 #define EBITMAP_SIZE        (EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE)
0030 #define EBITMAP_BIT     1ULL
0031 #define EBITMAP_SHIFT_UNIT_SIZE(x)                  \
0032     (((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2)
0033
0034 struct ebitmap_node {
0035     struct ebitmap_node *next;
0036     unsigned long maps[EBITMAP_UNIT_NUMS];
0037     u32 startbit;
0038 };
0039
0040 struct ebitmap {
0041     struct ebitmap_node *node;  /* first node in the bitmap */
0042     u32 highbit;    /* highest position in the total bitmap */
0043 };
0044
0045 #define ebitmap_length(e) ((e)->highbit)
0046
0047 static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
0048                           struct ebitmap_node **n)
0049 {
0050     unsigned int ofs;
0051
0052     for (*n = e->node; *n; *n = (*n)->next) {
0053         ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
0054         if (ofs < EBITMAP_SIZE)
0055             return (*n)->startbit + ofs;
0056     }
0057     return ebitmap_length(e);
0058 }
0059
0060 static inline void ebitmap_init(struct ebitmap *e)
0061 {
0062     memset(e, 0, sizeof(*e));
0063 }
0064
0065 static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
0066                          struct ebitmap_node **n,
0067                          unsigned int bit)
0068 {
0069     unsigned int ofs;
0070
0071     ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1);
0072     if (ofs < EBITMAP_SIZE)
0073         return ofs + (*n)->startbit;
0074
0075     for (*n = (*n)->next; *n; *n = (*n)->next) {
0076         ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
0077         if (ofs < EBITMAP_SIZE)
0078             return ofs + (*n)->startbit;
0079     }
0080     return ebitmap_length(e);
0081 }
0082
0083 #define EBITMAP_NODE_INDEX(node, bit)   \
0084     (((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE)
0085 #define EBITMAP_NODE_OFFSET(node, bit)  \
0086     (((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE)
0087
0088 static inline int ebitmap_node_get_bit(struct ebitmap_node *n,
0089                        unsigned int bit)
0090 {
0091     unsigned int index = EBITMAP_NODE_INDEX(n, bit);
0092     unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
0093
0094     BUG_ON(index >= EBITMAP_UNIT_NUMS);
0095     if ((n->maps[index] & (EBITMAP_BIT << ofs)))
0096         return 1;
0097     return 0;
0098 }
0099
0100 static inline void ebitmap_node_set_bit(struct ebitmap_node *n,
0101                     unsigned int bit)
0102 {
0103     unsigned int index = EBITMAP_NODE_INDEX(n, bit);
0104     unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
0105
0106     BUG_ON(index >= EBITMAP_UNIT_NUMS);
0107     n->maps[index] |= (EBITMAP_BIT << ofs);
0108 }
0109
0110 static inline void ebitmap_node_clr_bit(struct ebitmap_node *n,
0111                     unsigned int bit)
0112 {
0113     unsigned int index = EBITMAP_NODE_INDEX(n, bit);
0114     unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
0115
0116     BUG_ON(index >= EBITMAP_UNIT_NUMS);
0117     n->maps[index] &= ~(EBITMAP_BIT << ofs);
0118 }
0119
0120 #define ebitmap_for_each_positive_bit(e, n, bit)    \
0121     for ((bit) = ebitmap_start_positive(e, &(n));   \
0122          (bit) < ebitmap_length(e);         \
0123          (bit) = ebitmap_next_positive(e, &(n), bit))   \
0124
0125 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
0126 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);
0127 int ebitmap_and(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2);
0128 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit);
0129 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit);
0130 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value);
0131 void ebitmap_destroy(struct ebitmap *e);
0132 int ebitmap_read(struct ebitmap *e, void *fp);
0133 int ebitmap_write(struct ebitmap *e, void *fp);
0134 u32 ebitmap_hash(const struct ebitmap *e, u32 hash);
0135
0136 #ifdef CONFIG_NETLABEL
0137 int ebitmap_netlbl_export(struct ebitmap *ebmap,
0138               struct netlbl_lsm_catmap **catmap);
0139 int ebitmap_netlbl_import(struct ebitmap *ebmap,
0140               struct netlbl_lsm_catmap *catmap);
0141 #else
0142 static inline int ebitmap_netlbl_export(struct ebitmap *ebmap,
0143                     struct netlbl_lsm_catmap **catmap)
0144 {
0145     return -ENOMEM;
0146 }
0147 static inline int ebitmap_netlbl_import(struct ebitmap *ebmap,
0148                     struct netlbl_lsm_catmap *catmap)
0149 {
0150     return -ENOMEM;
0151 }
0152 #endif
0153
0154 #endif  /* _SS_EBITMAP_H_ */