[linux-2.6-block.git] / security / selinux / ss / ebitmap.h

/*
 * 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@epoch.ncsc.mil>
 */
#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);

#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
1da177e4 LT	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
02752760 PM	17	#include <net/netlabel.h>
02752760 PM	18
a767f680 WL	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))\
9fe79ad1 KK	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
087feb98 KK	30	#define EBITMAP_SHIFT_UNIT_SIZE(x) \
087feb98 KK	31	(((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2)
1da177e4 LT	32
1da177e4 LT	33	struct ebitmap_node {
1da177e4	34	struct ebitmap_node *next;
9fe79ad1 KK	35	unsigned long maps[EBITMAP_UNIT_NUMS];
9fe79ad1 KK	36	u32 startbit;
1da177e4 LT	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)
1da177e4	45
9fe79ad1 KK	46	static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
9fe79ad1 KK	47	struct ebitmap_node **n)
782ebb99	48	{
9fe79ad1 KK	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);
782ebb99 SS	57	}
782ebb99 SS	58
1da177e4 LT	59	static inline void ebitmap_init(struct ebitmap *e)
	60	{
	61	memset(e, 0, sizeof(*e));
	62	}
	63
9fe79ad1 KK	64	static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
	65	struct ebitmap_node **n,
	66	unsigned int bit)
782ebb99	67	{
9fe79ad1 KK	68	unsigned int ofs;
	69
	70	ofs = find_next_bit((n)->maps, EBITMAP_SIZE, bit - (n)->startbit + 1);
	71	if (ofs < EBITMAP_SIZE)
	72	return ofs + (*n)->startbit;
782ebb99	73
9fe79ad1 KK	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);
782ebb99 SS	80	}
782ebb99 SS	81
9fe79ad1 KK	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,
782ebb99 SS	88	unsigned int bit)
782ebb99 SS	89	{
9fe79ad1 KK	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)))
782ebb99 SS	95	return 1;
	96	return 0;
	97	}
	98
9fe79ad1 KK	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)) \
782ebb99	123
1da177e4 LT	124	int ebitmap_cmp(struct ebitmap e1, struct ebitmap e2);
1da177e4 LT	125	int ebitmap_cpy(struct ebitmap dst, struct ebitmap src);
fee71142	126	int ebitmap_contains(struct ebitmap e1, struct ebitmap e2, u32 last_e2bit);
1da177e4 LT	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);
cee74f47	131	int ebitmap_write(struct ebitmap e, void fp);
1da177e4	132
02752760 PM	133	#ifdef CONFIG_NETLABEL
02752760 PM	134	int ebitmap_netlbl_export(struct ebitmap *ebmap,
4fbe63d1	135	struct netlbl_lsm_catmap **catmap);
02752760	136	int ebitmap_netlbl_import(struct ebitmap *ebmap,
4fbe63d1	137	struct netlbl_lsm_catmap *catmap);
02752760 PM	138	#else
02752760 PM	139	static inline int ebitmap_netlbl_export(struct ebitmap *ebmap,
4fbe63d1	140	struct netlbl_lsm_catmap **catmap)
02752760 PM	141	{
	142	return -ENOMEM;
	143	}
	144	static inline int ebitmap_netlbl_import(struct ebitmap *ebmap,
4fbe63d1	145	struct netlbl_lsm_catmap *catmap)
02752760 PM	146	{
	147	return -ENOMEM;
	148	}
	149	#endif
	150
1da177e4	151	#endif /* _SS_EBITMAP_H_ */