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