11da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* 21da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * An extensible bitmap is a bitmap that supports an 31da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * arbitrary number of bits. Extensible bitmaps are 41da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * used to represent sets of values, such as types, 51da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * roles, categories, and classes. 61da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 71da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Each extensible bitmap is implemented as a linked 81da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * list of bitmap nodes, where each bitmap node has 91da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * an explicitly specified starting bit position within 101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * the total bitmap. 111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#ifndef _SS_EBITMAP_H_ 151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#define _SS_EBITMAP_H_ 161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1702752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore#include <net/netlabel.h> 1802752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore 19a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long#ifdef CONFIG_64BIT 20a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long#define EBITMAP_NODE_SIZE 64 21a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long#else 22a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long#define EBITMAP_NODE_SIZE 32 23a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long#endif 24a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long 25a767f680e34bf14a36fefbbb6d85783eef99fd57Waiman Long#define EBITMAP_UNIT_NUMS ((EBITMAP_NODE_SIZE-sizeof(void *)-sizeof(u32))\ 269fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei / sizeof(unsigned long)) 279fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei#define EBITMAP_UNIT_SIZE BITS_PER_LONG 289fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei#define EBITMAP_SIZE (EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE) 299fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei#define EBITMAP_BIT 1ULL 30087feb980443aadc7c62f6c26d3867543b470d8cKaiGai Kohei#define EBITMAP_SHIFT_UNIT_SIZE(x) \ 31087feb980443aadc7c62f6c26d3867543b470d8cKaiGai Kohei (((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2) 321da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstruct ebitmap_node { 341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct ebitmap_node *next; 359fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned long maps[EBITMAP_UNIT_NUMS]; 369fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei u32 startbit; 371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 391da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstruct ebitmap { 401da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct ebitmap_node *node; /* first node in the bitmap */ 411da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds u32 highbit; /* highest position in the total bitmap */ 421da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 431da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 441da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#define ebitmap_length(e) ((e)->highbit) 451da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 469fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Koheistatic inline unsigned int ebitmap_start_positive(struct ebitmap *e, 479fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei struct ebitmap_node **n) 48782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley{ 499fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int ofs; 509fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 519fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei for (*n = e->node; *n; *n = (*n)->next) { 529fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); 539fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei if (ofs < EBITMAP_SIZE) 549fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei return (*n)->startbit + ofs; 559fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei } 569fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei return ebitmap_length(e); 57782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley} 58782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley 591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic inline void ebitmap_init(struct ebitmap *e) 601da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 611da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds memset(e, 0, sizeof(*e)); 621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 649fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Koheistatic inline unsigned int ebitmap_next_positive(struct ebitmap *e, 659fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei struct ebitmap_node **n, 669fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int bit) 67782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley{ 689fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int ofs; 699fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 709fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1); 719fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei if (ofs < EBITMAP_SIZE) 729fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei return ofs + (*n)->startbit; 73782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley 749fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei for (*n = (*n)->next; *n; *n = (*n)->next) { 759fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei ofs = find_first_bit((*n)->maps, EBITMAP_SIZE); 769fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei if (ofs < EBITMAP_SIZE) 779fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei return ofs + (*n)->startbit; 789fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei } 799fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei return ebitmap_length(e); 80782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley} 81782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley 829fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei#define EBITMAP_NODE_INDEX(node, bit) \ 839fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei (((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE) 849fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei#define EBITMAP_NODE_OFFSET(node, bit) \ 859fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei (((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE) 869fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 879fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Koheistatic inline int ebitmap_node_get_bit(struct ebitmap_node *n, 88782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley unsigned int bit) 89782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley{ 909fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int index = EBITMAP_NODE_INDEX(n, bit); 919fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 929fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 939fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei BUG_ON(index >= EBITMAP_UNIT_NUMS); 949fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei if ((n->maps[index] & (EBITMAP_BIT << ofs))) 95782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley return 1; 96782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley return 0; 97782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley} 98782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley 999fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Koheistatic inline void ebitmap_node_set_bit(struct ebitmap_node *n, 1009fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int bit) 1019fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei{ 1029fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int index = EBITMAP_NODE_INDEX(n, bit); 1039fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 1049fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 1059fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei BUG_ON(index >= EBITMAP_UNIT_NUMS); 1069fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei n->maps[index] |= (EBITMAP_BIT << ofs); 1079fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei} 1089fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 1099fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Koheistatic inline void ebitmap_node_clr_bit(struct ebitmap_node *n, 1109fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int bit) 1119fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei{ 1129fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int index = EBITMAP_NODE_INDEX(n, bit); 1139fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit); 1149fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 1159fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei BUG_ON(index >= EBITMAP_UNIT_NUMS); 1169fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei n->maps[index] &= ~(EBITMAP_BIT << ofs); 1179fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei} 1189fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei 1199fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei#define ebitmap_for_each_positive_bit(e, n, bit) \ 1209fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei for (bit = ebitmap_start_positive(e, &n); \ 1219fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei bit < ebitmap_length(e); \ 1229fe79ad1e43d236bbbb8edb3cf634356de714c79KaiGai Kohei bit = ebitmap_next_positive(e, &n, bit)) \ 123782ebb992ec20b5afdd5786ee8c2f1b58b631f24Stephen Smalley 1241da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsint ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2); 1251da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsint ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src); 126fee7114298cf54bbd221cdb2ab49738be8b94f4cWaiman Longint ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit); 1271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsint ebitmap_get_bit(struct ebitmap *e, unsigned long bit); 1281da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsint ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value); 1291da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsvoid ebitmap_destroy(struct ebitmap *e); 1301da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsint ebitmap_read(struct ebitmap *e, void *fp); 131cee74f47a6baba0ac457e87687fdcf0abd599f0aEric Parisint ebitmap_write(struct ebitmap *e, void *fp); 1321da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 13302752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore#ifdef CONFIG_NETLABEL 13402752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Mooreint ebitmap_netlbl_export(struct ebitmap *ebmap, 1354fbe63d1c773cceef3fe1f6ed0c9c268f4f24760Paul Moore struct netlbl_lsm_catmap **catmap); 13602752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Mooreint ebitmap_netlbl_import(struct ebitmap *ebmap, 1374fbe63d1c773cceef3fe1f6ed0c9c268f4f24760Paul Moore struct netlbl_lsm_catmap *catmap); 13802752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore#else 13902752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moorestatic inline int ebitmap_netlbl_export(struct ebitmap *ebmap, 1404fbe63d1c773cceef3fe1f6ed0c9c268f4f24760Paul Moore struct netlbl_lsm_catmap **catmap) 14102752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore{ 14202752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore return -ENOMEM; 14302752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore} 14402752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moorestatic inline int ebitmap_netlbl_import(struct ebitmap *ebmap, 1454fbe63d1c773cceef3fe1f6ed0c9c268f4f24760Paul Moore struct netlbl_lsm_catmap *catmap) 14602752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore{ 14702752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore return -ENOMEM; 14802752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore} 14902752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore#endif 15002752760359db6b00a3ffb1acfc13ef8d9eb1e3fPaul Moore 1511da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#endif /* _SS_EBITMAP_H_ */ 152