[mirror_ubuntu-bionic-kernel.git] / security / selinux / ss / ebitmap.h

/* SPDX-License-Identifier: GPL-2.0 */
/*
 * An extensible bitmap is a bitmap that supports an
 * arbitrary number of bits.  Extensible bitmaps are
 * used to represent sets of values, such as types,
 * roles, categories, and classes.
 *
 * Each extensible bitmap is implemented as a linked
 * list of bitmap nodes, where each bitmap node has
 * an explicitly specified starting bit position within
 * the total bitmap.
 *
 * Author : Stephen Smalley, <sds@tycho.nsa.gov>
 */
#ifndef _SS_EBITMAP_H_
#define _SS_EBITMAP_H_

#include <net/netlabel.h>

#ifdef CONFIG_64BIT
#define	EBITMAP_NODE_SIZE	64
#else
#define	EBITMAP_NODE_SIZE	32
#endif

#define EBITMAP_UNIT_NUMS	((EBITMAP_NODE_SIZE-sizeof(void *)-sizeof(u32))\
					/ sizeof(unsigned long))
#define EBITMAP_UNIT_SIZE	BITS_PER_LONG
#define EBITMAP_SIZE		(EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE)
#define EBITMAP_BIT		1ULL
#define EBITMAP_SHIFT_UNIT_SIZE(x)					\
	(((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2)

struct ebitmap_node {
	struct ebitmap_node *next;
	unsigned long maps[EBITMAP_UNIT_NUMS];
	u32 startbit;
};

struct ebitmap {
	struct ebitmap_node *node;	/* first node in the bitmap */
	u32 highbit;	/* highest position in the total bitmap */
};

#define ebitmap_length(e) ((e)->highbit)

static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
						  struct ebitmap_node **n)
{
	unsigned int ofs;

	for (*n = e->node; *n; *n = (*n)->next) {
		ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
		if (ofs < EBITMAP_SIZE)
			return (*n)->startbit + ofs;
	}
	return ebitmap_length(e);
}

static inline void ebitmap_init(struct ebitmap *e)
{
	memset(e, 0, sizeof(*e));
}

static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
						 struct ebitmap_node **n,
						 unsigned int bit)
{
	unsigned int ofs;

	ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1);
	if (ofs < EBITMAP_SIZE)
		return ofs + (*n)->startbit;

	for (*n = (*n)->next; *n; *n = (*n)->next) {
		ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
		if (ofs < EBITMAP_SIZE)
			return ofs + (*n)->startbit;
	}
	return ebitmap_length(e);
}

#define EBITMAP_NODE_INDEX(node, bit)	\
	(((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE)
#define EBITMAP_NODE_OFFSET(node, bit)	\
	(((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE)

static inline int ebitmap_node_get_bit(struct ebitmap_node *n,
				       unsigned int bit)
{
	unsigned int index = EBITMAP_NODE_INDEX(n, bit);
	unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);

	BUG_ON(index >= EBITMAP_UNIT_NUMS);
	if ((n->maps[index] & (EBITMAP_BIT << ofs)))
		return 1;
	return 0;
}

static inline void ebitmap_node_set_bit(struct ebitmap_node *n,
					unsigned int bit)
{
	unsigned int index = EBITMAP_NODE_INDEX(n, bit);
	unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);

	BUG_ON(index >= EBITMAP_UNIT_NUMS);
	n->maps[index] |= (EBITMAP_BIT << ofs);
}

static inline void ebitmap_node_clr_bit(struct ebitmap_node *n,
					unsigned int bit)
{
	unsigned int index = EBITMAP_NODE_INDEX(n, bit);
	unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);

	BUG_ON(index >= EBITMAP_UNIT_NUMS);
	n->maps[index] &= ~(EBITMAP_BIT << ofs);
}

#define ebitmap_for_each_positive_bit(e, n, bit)	\
	for (bit = ebitmap_start_positive(e, &n);	\
	     bit < ebitmap_length(e);			\
	     bit = ebitmap_next_positive(e, &n, bit))	\

int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);
int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit);
int ebitmap_get_bit(struct ebitmap *e, unsigned long bit);
int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value);
void ebitmap_destroy(struct ebitmap *e);
int ebitmap_read(struct ebitmap *e, void *fp);
int ebitmap_write(struct ebitmap *e, void *fp);

void ebitmap_cache_init(void);
void ebitmap_cache_destroy(void);

#ifdef CONFIG_NETLABEL
int ebitmap_netlbl_export(struct ebitmap *ebmap,
			  struct netlbl_lsm_catmap **catmap);
int ebitmap_netlbl_import(struct ebitmap *ebmap,
			  struct netlbl_lsm_catmap *catmap);
#else
static inline int ebitmap_netlbl_export(struct ebitmap *ebmap,
					struct netlbl_lsm_catmap **catmap)
{
	return -ENOMEM;
}
static inline int ebitmap_netlbl_import(struct ebitmap *ebmap,
					struct netlbl_lsm_catmap *catmap)
{
	return -ENOMEM;
}
#endif

#endif	/* _SS_EBITMAP_H_ */
Commit	Line	Data
b2441318	1	/* SPDX-License-Identifier: GPL-2.0 */
1da177e4 LT	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	*
7efbb60b	13	* Author : Stephen Smalley, <sds@tycho.nsa.gov>
1da177e4 LT	14	*/
	15	#ifndef _SS_EBITMAP_H_
	16	#define _SS_EBITMAP_H_
	17
02752760 PM	18	#include <net/netlabel.h>
02752760 PM	19
a767f680 WL	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))\
9fe79ad1 KK	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
087feb98 KK	31	#define EBITMAP_SHIFT_UNIT_SIZE(x) \
087feb98 KK	32	(((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2)
1da177e4 LT	33
1da177e4 LT	34	struct ebitmap_node {
1da177e4	35	struct ebitmap_node *next;
9fe79ad1 KK	36	unsigned long maps[EBITMAP_UNIT_NUMS];
9fe79ad1 KK	37	u32 startbit;
1da177e4 LT	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)
1da177e4	46
9fe79ad1 KK	47	static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
9fe79ad1 KK	48	struct ebitmap_node **n)
782ebb99	49	{
9fe79ad1 KK	50	unsigned int ofs;
	51
	52	for (n = e->node; n; n = (n)->next) {
	53	ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
	54	if (ofs < EBITMAP_SIZE)
	55	return (*n)->startbit + ofs;
	56	}
	57	return ebitmap_length(e);
782ebb99 SS	58	}
782ebb99 SS	59
1da177e4 LT	60	static inline void ebitmap_init(struct ebitmap *e)
	61	{
	62	memset(e, 0, sizeof(*e));
	63	}
	64
9fe79ad1 KK	65	static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
	66	struct ebitmap_node **n,
	67	unsigned int bit)
782ebb99	68	{
9fe79ad1 KK	69	unsigned int ofs;
	70
	71	ofs = find_next_bit((n)->maps, EBITMAP_SIZE, bit - (n)->startbit + 1);
	72	if (ofs < EBITMAP_SIZE)
	73	return ofs + (*n)->startbit;
782ebb99	74
9fe79ad1 KK	75	for (n = (n)->next; n; n = (*n)->next) {
	76	ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
	77	if (ofs < EBITMAP_SIZE)
	78	return ofs + (*n)->startbit;
	79	}
	80	return ebitmap_length(e);
782ebb99 SS	81	}
782ebb99 SS	82
9fe79ad1 KK	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(struct ebitmap_node *n,
782ebb99 SS	89	unsigned int bit)
782ebb99 SS	90	{
9fe79ad1 KK	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)))
782ebb99 SS	96	return 1;
	97	return 0;
	98	}
	99
9fe79ad1 KK	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)) \
782ebb99	124
1da177e4 LT	125	int ebitmap_cmp(struct ebitmap e1, struct ebitmap e2);
1da177e4 LT	126	int ebitmap_cpy(struct ebitmap dst, struct ebitmap src);
fee71142	127	int ebitmap_contains(struct ebitmap e1, struct ebitmap e2, u32 last_e2bit);
1da177e4 LT	128	int ebitmap_get_bit(struct ebitmap *e, unsigned long bit);
	129	int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value);
	130	void ebitmap_destroy(struct ebitmap *e);
	131	int ebitmap_read(struct ebitmap e, void fp);
cee74f47	132	int ebitmap_write(struct ebitmap e, void fp);
1da177e4	133
b4958c89 JL	134	void ebitmap_cache_init(void);
	135	void ebitmap_cache_destroy(void);
	136
02752760 PM	137	#ifdef CONFIG_NETLABEL
02752760 PM	138	int ebitmap_netlbl_export(struct ebitmap *ebmap,
4fbe63d1	139	struct netlbl_lsm_catmap **catmap);
02752760	140	int ebitmap_netlbl_import(struct ebitmap *ebmap,
4fbe63d1	141	struct netlbl_lsm_catmap *catmap);
02752760 PM	142	#else
02752760 PM	143	static inline int ebitmap_netlbl_export(struct ebitmap *ebmap,
4fbe63d1	144	struct netlbl_lsm_catmap **catmap)
02752760 PM	145	{
	146	return -ENOMEM;
	147	}
	148	static inline int ebitmap_netlbl_import(struct ebitmap *ebmap,
4fbe63d1	149	struct netlbl_lsm_catmap *catmap)
02752760 PM	150	{
	151	return -ENOMEM;
	152	}
	153	#endif
	154
1da177e4	155	#endif /* _SS_EBITMAP_H_ */