1255e72915d4cbddceb435e13d81601755714e9fSE Android 2255e72915d4cbddceb435e13d81601755714e9fSE Android/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */ 3255e72915d4cbddceb435e13d81601755714e9fSE Android 4255e72915d4cbddceb435e13d81601755714e9fSE Android/* FLASK */ 5255e72915d4cbddceb435e13d81601755714e9fSE Android 6255e72915d4cbddceb435e13d81601755714e9fSE Android/* 7255e72915d4cbddceb435e13d81601755714e9fSE Android * Implementation of the extensible bitmap type. 8255e72915d4cbddceb435e13d81601755714e9fSE Android */ 9255e72915d4cbddceb435e13d81601755714e9fSE Android 10255e72915d4cbddceb435e13d81601755714e9fSE Android#include <stdlib.h> 11255e72915d4cbddceb435e13d81601755714e9fSE Android 12255e72915d4cbddceb435e13d81601755714e9fSE Android#include <sepol/policydb/ebitmap.h> 13255e72915d4cbddceb435e13d81601755714e9fSE Android#include <sepol/policydb/policydb.h> 14255e72915d4cbddceb435e13d81601755714e9fSE Android 15255e72915d4cbddceb435e13d81601755714e9fSE Android#include "debug.h" 16255e72915d4cbddceb435e13d81601755714e9fSE Android#include "private.h" 17255e72915d4cbddceb435e13d81601755714e9fSE Android 18255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2) 19255e72915d4cbddceb435e13d81601755714e9fSE Android{ 20255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n1, *n2, *new, *prev; 21255e72915d4cbddceb435e13d81601755714e9fSE Android 22255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_init(dst); 23255e72915d4cbddceb435e13d81601755714e9fSE Android 24255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = e1->node; 25255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = e2->node; 26255e72915d4cbddceb435e13d81601755714e9fSE Android prev = 0; 27255e72915d4cbddceb435e13d81601755714e9fSE Android while (n1 || n2) { 28255e72915d4cbddceb435e13d81601755714e9fSE Android new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t)); 29255e72915d4cbddceb435e13d81601755714e9fSE Android if (!new) { 30255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_destroy(dst); 31255e72915d4cbddceb435e13d81601755714e9fSE Android return -ENOMEM; 32255e72915d4cbddceb435e13d81601755714e9fSE Android } 33255e72915d4cbddceb435e13d81601755714e9fSE Android memset(new, 0, sizeof(ebitmap_node_t)); 34255e72915d4cbddceb435e13d81601755714e9fSE Android if (n1 && n2 && n1->startbit == n2->startbit) { 35255e72915d4cbddceb435e13d81601755714e9fSE Android new->startbit = n1->startbit; 36255e72915d4cbddceb435e13d81601755714e9fSE Android new->map = n1->map | n2->map; 37255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = n1->next; 38255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = n2->next; 39255e72915d4cbddceb435e13d81601755714e9fSE Android } else if (!n2 || (n1 && n1->startbit < n2->startbit)) { 40255e72915d4cbddceb435e13d81601755714e9fSE Android new->startbit = n1->startbit; 41255e72915d4cbddceb435e13d81601755714e9fSE Android new->map = n1->map; 42255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = n1->next; 43255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 44255e72915d4cbddceb435e13d81601755714e9fSE Android new->startbit = n2->startbit; 45255e72915d4cbddceb435e13d81601755714e9fSE Android new->map = n2->map; 46255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = n2->next; 47255e72915d4cbddceb435e13d81601755714e9fSE Android } 48255e72915d4cbddceb435e13d81601755714e9fSE Android 49255e72915d4cbddceb435e13d81601755714e9fSE Android new->next = 0; 50255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) 51255e72915d4cbddceb435e13d81601755714e9fSE Android prev->next = new; 52255e72915d4cbddceb435e13d81601755714e9fSE Android else 53255e72915d4cbddceb435e13d81601755714e9fSE Android dst->node = new; 54255e72915d4cbddceb435e13d81601755714e9fSE Android prev = new; 55255e72915d4cbddceb435e13d81601755714e9fSE Android } 56255e72915d4cbddceb435e13d81601755714e9fSE Android 57255e72915d4cbddceb435e13d81601755714e9fSE Android dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit; 58255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 59255e72915d4cbddceb435e13d81601755714e9fSE Android} 60255e72915d4cbddceb435e13d81601755714e9fSE Android 61255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1) 62255e72915d4cbddceb435e13d81601755714e9fSE Android{ 63255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_t tmp; 64255e72915d4cbddceb435e13d81601755714e9fSE Android 65255e72915d4cbddceb435e13d81601755714e9fSE Android if (ebitmap_or(&tmp, dst, e1)) 66255e72915d4cbddceb435e13d81601755714e9fSE Android return -1; 67255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_destroy(dst); 68255e72915d4cbddceb435e13d81601755714e9fSE Android dst->node = tmp.node; 69255e72915d4cbddceb435e13d81601755714e9fSE Android dst->highbit = tmp.highbit; 70255e72915d4cbddceb435e13d81601755714e9fSE Android 71255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 72255e72915d4cbddceb435e13d81601755714e9fSE Android} 73255e72915d4cbddceb435e13d81601755714e9fSE Android 74fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyint ebitmap_and(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2) 75fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley{ 76fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley unsigned int i, length = min(ebitmap_length(e1), ebitmap_length(e2)); 77fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_init(dst); 78fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley for (i=0; i < length; i++) { 79fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (ebitmap_get_bit(e1, i) && ebitmap_get_bit(e2, i)) { 80fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int rc = ebitmap_set_bit(dst, i, 1); 81fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (rc < 0) 82fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return rc; 83fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley } 84fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley } 85fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return 0; 86fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley} 87fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley 88fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyint ebitmap_xor(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2) 89fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley{ 90fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley unsigned int i, length = max(ebitmap_length(e1), ebitmap_length(e2)); 91fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_init(dst); 92fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley for (i=0; i < length; i++) { 93fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int val = ebitmap_get_bit(e1, i) ^ ebitmap_get_bit(e2, i); 94fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int rc = ebitmap_set_bit(dst, i, val); 95fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (rc < 0) 96fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return rc; 97fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley } 98fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return 0; 99fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley} 100fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley 101fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyint ebitmap_not(ebitmap_t *dst, ebitmap_t *e1, unsigned int maxbit) 102fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley{ 103fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley unsigned int i; 104fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_init(dst); 105fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley for (i=0; i < maxbit; i++) { 106fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int val = ebitmap_get_bit(e1, i); 107fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int rc = ebitmap_set_bit(dst, i, !val); 108fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (rc < 0) 109fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return rc; 110fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley } 111fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return 0; 112fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley} 113fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley 114fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyint ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int maxbit) 115fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley{ 116fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_t e3; 117fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_init(dst); 118fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int rc = ebitmap_not(&e3, e2, maxbit); 119fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (rc < 0) 120fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return rc; 121fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley rc = ebitmap_and(dst, e1, &e3); 122fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_destroy(&e3); 123fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (rc < 0) 124fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return rc; 125fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return 0; 126fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley} 127fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley 128fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyunsigned int ebitmap_cardinality(ebitmap_t *e1) 129fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley{ 130fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley unsigned int i, count = 0; 131fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++) 132fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (ebitmap_get_bit(e1, i)) 133fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley count++; 134fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return count; 135fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley} 136fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley 137fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyint ebitmap_hamming_distance(ebitmap_t * e1, ebitmap_t * e2) 138fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley{ 139fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (ebitmap_cmp(e1, e2)) 140fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return 0; 141fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_t tmp; 142fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int rc = ebitmap_xor(&tmp, e1, e2); 143fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley if (rc < 0) 144fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return -1; 145fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley int distance = ebitmap_cardinality(&tmp); 146fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley ebitmap_destroy(&tmp); 147fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley return distance; 148fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley} 149fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalley 150255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2) 151255e72915d4cbddceb435e13d81601755714e9fSE Android{ 152255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n1, *n2; 153255e72915d4cbddceb435e13d81601755714e9fSE Android 154255e72915d4cbddceb435e13d81601755714e9fSE Android if (e1->highbit != e2->highbit) 155255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 156255e72915d4cbddceb435e13d81601755714e9fSE Android 157255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = e1->node; 158255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = e2->node; 159255e72915d4cbddceb435e13d81601755714e9fSE Android while (n1 && n2 && 160255e72915d4cbddceb435e13d81601755714e9fSE Android (n1->startbit == n2->startbit) && (n1->map == n2->map)) { 161255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = n1->next; 162255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = n2->next; 163255e72915d4cbddceb435e13d81601755714e9fSE Android } 164255e72915d4cbddceb435e13d81601755714e9fSE Android 165255e72915d4cbddceb435e13d81601755714e9fSE Android if (n1 || n2) 166255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 167255e72915d4cbddceb435e13d81601755714e9fSE Android 168255e72915d4cbddceb435e13d81601755714e9fSE Android return 1; 169255e72915d4cbddceb435e13d81601755714e9fSE Android} 170255e72915d4cbddceb435e13d81601755714e9fSE Android 171255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src) 172255e72915d4cbddceb435e13d81601755714e9fSE Android{ 173255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n, *new, *prev; 174255e72915d4cbddceb435e13d81601755714e9fSE Android 175255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_init(dst); 176255e72915d4cbddceb435e13d81601755714e9fSE Android n = src->node; 177255e72915d4cbddceb435e13d81601755714e9fSE Android prev = 0; 178255e72915d4cbddceb435e13d81601755714e9fSE Android while (n) { 179255e72915d4cbddceb435e13d81601755714e9fSE Android new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t)); 180255e72915d4cbddceb435e13d81601755714e9fSE Android if (!new) { 181255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_destroy(dst); 182255e72915d4cbddceb435e13d81601755714e9fSE Android return -ENOMEM; 183255e72915d4cbddceb435e13d81601755714e9fSE Android } 184255e72915d4cbddceb435e13d81601755714e9fSE Android memset(new, 0, sizeof(ebitmap_node_t)); 185255e72915d4cbddceb435e13d81601755714e9fSE Android new->startbit = n->startbit; 186255e72915d4cbddceb435e13d81601755714e9fSE Android new->map = n->map; 187255e72915d4cbddceb435e13d81601755714e9fSE Android new->next = 0; 188255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) 189255e72915d4cbddceb435e13d81601755714e9fSE Android prev->next = new; 190255e72915d4cbddceb435e13d81601755714e9fSE Android else 191255e72915d4cbddceb435e13d81601755714e9fSE Android dst->node = new; 192255e72915d4cbddceb435e13d81601755714e9fSE Android prev = new; 193255e72915d4cbddceb435e13d81601755714e9fSE Android n = n->next; 194255e72915d4cbddceb435e13d81601755714e9fSE Android } 195255e72915d4cbddceb435e13d81601755714e9fSE Android 196255e72915d4cbddceb435e13d81601755714e9fSE Android dst->highbit = src->highbit; 197255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 198255e72915d4cbddceb435e13d81601755714e9fSE Android} 199255e72915d4cbddceb435e13d81601755714e9fSE Android 200255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2) 201255e72915d4cbddceb435e13d81601755714e9fSE Android{ 202255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n1, *n2; 203255e72915d4cbddceb435e13d81601755714e9fSE Android 204255e72915d4cbddceb435e13d81601755714e9fSE Android if (e1->highbit < e2->highbit) 205255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 206255e72915d4cbddceb435e13d81601755714e9fSE Android 207255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = e1->node; 208255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = e2->node; 209255e72915d4cbddceb435e13d81601755714e9fSE Android while (n1 && n2 && (n1->startbit <= n2->startbit)) { 210255e72915d4cbddceb435e13d81601755714e9fSE Android if (n1->startbit < n2->startbit) { 211255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = n1->next; 212255e72915d4cbddceb435e13d81601755714e9fSE Android continue; 213255e72915d4cbddceb435e13d81601755714e9fSE Android } 214255e72915d4cbddceb435e13d81601755714e9fSE Android if ((n1->map & n2->map) != n2->map) 215255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 216255e72915d4cbddceb435e13d81601755714e9fSE Android 217255e72915d4cbddceb435e13d81601755714e9fSE Android n1 = n1->next; 218255e72915d4cbddceb435e13d81601755714e9fSE Android n2 = n2->next; 219255e72915d4cbddceb435e13d81601755714e9fSE Android } 220255e72915d4cbddceb435e13d81601755714e9fSE Android 221255e72915d4cbddceb435e13d81601755714e9fSE Android if (n2) 222255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 223255e72915d4cbddceb435e13d81601755714e9fSE Android 224255e72915d4cbddceb435e13d81601755714e9fSE Android return 1; 225255e72915d4cbddceb435e13d81601755714e9fSE Android} 226255e72915d4cbddceb435e13d81601755714e9fSE Android 227255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_get_bit(const ebitmap_t * e, unsigned int bit) 228255e72915d4cbddceb435e13d81601755714e9fSE Android{ 229255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n; 230255e72915d4cbddceb435e13d81601755714e9fSE Android 231255e72915d4cbddceb435e13d81601755714e9fSE Android if (e->highbit < bit) 232255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 233255e72915d4cbddceb435e13d81601755714e9fSE Android 234255e72915d4cbddceb435e13d81601755714e9fSE Android n = e->node; 235255e72915d4cbddceb435e13d81601755714e9fSE Android while (n && (n->startbit <= bit)) { 236255e72915d4cbddceb435e13d81601755714e9fSE Android if ((n->startbit + MAPSIZE) > bit) { 237255e72915d4cbddceb435e13d81601755714e9fSE Android if (n->map & (MAPBIT << (bit - n->startbit))) 238255e72915d4cbddceb435e13d81601755714e9fSE Android return 1; 239255e72915d4cbddceb435e13d81601755714e9fSE Android else 240255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 241255e72915d4cbddceb435e13d81601755714e9fSE Android } 242255e72915d4cbddceb435e13d81601755714e9fSE Android n = n->next; 243255e72915d4cbddceb435e13d81601755714e9fSE Android } 244255e72915d4cbddceb435e13d81601755714e9fSE Android 245255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 246255e72915d4cbddceb435e13d81601755714e9fSE Android} 247255e72915d4cbddceb435e13d81601755714e9fSE Android 248255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value) 249255e72915d4cbddceb435e13d81601755714e9fSE Android{ 250255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n, *prev, *new; 251255e72915d4cbddceb435e13d81601755714e9fSE Android uint32_t startbit = bit & ~(MAPSIZE - 1); 252255e72915d4cbddceb435e13d81601755714e9fSE Android uint32_t highbit = startbit + MAPSIZE; 253255e72915d4cbddceb435e13d81601755714e9fSE Android 254255e72915d4cbddceb435e13d81601755714e9fSE Android if (highbit == 0) { 255255e72915d4cbddceb435e13d81601755714e9fSE Android ERR(NULL, "bitmap overflow, bit 0x%x", bit); 256255e72915d4cbddceb435e13d81601755714e9fSE Android return -EINVAL; 257255e72915d4cbddceb435e13d81601755714e9fSE Android } 258255e72915d4cbddceb435e13d81601755714e9fSE Android 259255e72915d4cbddceb435e13d81601755714e9fSE Android prev = 0; 260255e72915d4cbddceb435e13d81601755714e9fSE Android n = e->node; 261255e72915d4cbddceb435e13d81601755714e9fSE Android while (n && n->startbit <= bit) { 262255e72915d4cbddceb435e13d81601755714e9fSE Android if ((n->startbit + MAPSIZE) > bit) { 263255e72915d4cbddceb435e13d81601755714e9fSE Android if (value) { 264255e72915d4cbddceb435e13d81601755714e9fSE Android n->map |= (MAPBIT << (bit - n->startbit)); 265255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 266255e72915d4cbddceb435e13d81601755714e9fSE Android n->map &= ~(MAPBIT << (bit - n->startbit)); 267255e72915d4cbddceb435e13d81601755714e9fSE Android if (!n->map) { 268255e72915d4cbddceb435e13d81601755714e9fSE Android /* drop this node from the bitmap */ 269255e72915d4cbddceb435e13d81601755714e9fSE Android 270255e72915d4cbddceb435e13d81601755714e9fSE Android if (!n->next) { 271255e72915d4cbddceb435e13d81601755714e9fSE Android /* 272255e72915d4cbddceb435e13d81601755714e9fSE Android * this was the highest map 273255e72915d4cbddceb435e13d81601755714e9fSE Android * within the bitmap 274255e72915d4cbddceb435e13d81601755714e9fSE Android */ 275255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) 276255e72915d4cbddceb435e13d81601755714e9fSE Android e->highbit = 277255e72915d4cbddceb435e13d81601755714e9fSE Android prev->startbit + 278255e72915d4cbddceb435e13d81601755714e9fSE Android MAPSIZE; 279255e72915d4cbddceb435e13d81601755714e9fSE Android else 280255e72915d4cbddceb435e13d81601755714e9fSE Android e->highbit = 0; 281255e72915d4cbddceb435e13d81601755714e9fSE Android } 282255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) 283255e72915d4cbddceb435e13d81601755714e9fSE Android prev->next = n->next; 284255e72915d4cbddceb435e13d81601755714e9fSE Android else 285255e72915d4cbddceb435e13d81601755714e9fSE Android e->node = n->next; 286255e72915d4cbddceb435e13d81601755714e9fSE Android 287255e72915d4cbddceb435e13d81601755714e9fSE Android free(n); 288255e72915d4cbddceb435e13d81601755714e9fSE Android } 289255e72915d4cbddceb435e13d81601755714e9fSE Android } 290255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 291255e72915d4cbddceb435e13d81601755714e9fSE Android } 292255e72915d4cbddceb435e13d81601755714e9fSE Android prev = n; 293255e72915d4cbddceb435e13d81601755714e9fSE Android n = n->next; 294255e72915d4cbddceb435e13d81601755714e9fSE Android } 295255e72915d4cbddceb435e13d81601755714e9fSE Android 296255e72915d4cbddceb435e13d81601755714e9fSE Android if (!value) 297255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 298255e72915d4cbddceb435e13d81601755714e9fSE Android 299255e72915d4cbddceb435e13d81601755714e9fSE Android new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t)); 300255e72915d4cbddceb435e13d81601755714e9fSE Android if (!new) 301255e72915d4cbddceb435e13d81601755714e9fSE Android return -ENOMEM; 302255e72915d4cbddceb435e13d81601755714e9fSE Android memset(new, 0, sizeof(ebitmap_node_t)); 303255e72915d4cbddceb435e13d81601755714e9fSE Android 304255e72915d4cbddceb435e13d81601755714e9fSE Android new->startbit = startbit; 305255e72915d4cbddceb435e13d81601755714e9fSE Android new->map = (MAPBIT << (bit - new->startbit)); 306255e72915d4cbddceb435e13d81601755714e9fSE Android 307255e72915d4cbddceb435e13d81601755714e9fSE Android if (!n) { 308255e72915d4cbddceb435e13d81601755714e9fSE Android /* this node will be the highest map within the bitmap */ 309255e72915d4cbddceb435e13d81601755714e9fSE Android e->highbit = highbit; 310255e72915d4cbddceb435e13d81601755714e9fSE Android } 311255e72915d4cbddceb435e13d81601755714e9fSE Android 312255e72915d4cbddceb435e13d81601755714e9fSE Android if (prev) { 313255e72915d4cbddceb435e13d81601755714e9fSE Android new->next = prev->next; 314255e72915d4cbddceb435e13d81601755714e9fSE Android prev->next = new; 315255e72915d4cbddceb435e13d81601755714e9fSE Android } else { 316255e72915d4cbddceb435e13d81601755714e9fSE Android new->next = e->node; 317255e72915d4cbddceb435e13d81601755714e9fSE Android e->node = new; 318255e72915d4cbddceb435e13d81601755714e9fSE Android } 319255e72915d4cbddceb435e13d81601755714e9fSE Android 320255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 321255e72915d4cbddceb435e13d81601755714e9fSE Android} 322255e72915d4cbddceb435e13d81601755714e9fSE Android 323255e72915d4cbddceb435e13d81601755714e9fSE Androidvoid ebitmap_destroy(ebitmap_t * e) 324255e72915d4cbddceb435e13d81601755714e9fSE Android{ 325255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n, *temp; 326255e72915d4cbddceb435e13d81601755714e9fSE Android 327255e72915d4cbddceb435e13d81601755714e9fSE Android if (!e) 328255e72915d4cbddceb435e13d81601755714e9fSE Android return; 329255e72915d4cbddceb435e13d81601755714e9fSE Android 330255e72915d4cbddceb435e13d81601755714e9fSE Android n = e->node; 331255e72915d4cbddceb435e13d81601755714e9fSE Android while (n) { 332255e72915d4cbddceb435e13d81601755714e9fSE Android temp = n; 333255e72915d4cbddceb435e13d81601755714e9fSE Android n = n->next; 334255e72915d4cbddceb435e13d81601755714e9fSE Android free(temp); 335255e72915d4cbddceb435e13d81601755714e9fSE Android } 336255e72915d4cbddceb435e13d81601755714e9fSE Android 337255e72915d4cbddceb435e13d81601755714e9fSE Android e->highbit = 0; 338255e72915d4cbddceb435e13d81601755714e9fSE Android e->node = 0; 339255e72915d4cbddceb435e13d81601755714e9fSE Android return; 340255e72915d4cbddceb435e13d81601755714e9fSE Android} 341255e72915d4cbddceb435e13d81601755714e9fSE Android 342255e72915d4cbddceb435e13d81601755714e9fSE Androidint ebitmap_read(ebitmap_t * e, void *fp) 343255e72915d4cbddceb435e13d81601755714e9fSE Android{ 344255e72915d4cbddceb435e13d81601755714e9fSE Android int rc; 345255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *n, *l; 346255e72915d4cbddceb435e13d81601755714e9fSE Android uint32_t buf[3], mapsize, count, i; 347255e72915d4cbddceb435e13d81601755714e9fSE Android uint64_t map; 348255e72915d4cbddceb435e13d81601755714e9fSE Android 349255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_init(e); 350255e72915d4cbddceb435e13d81601755714e9fSE Android 351255e72915d4cbddceb435e13d81601755714e9fSE Android rc = next_entry(buf, fp, sizeof(uint32_t) * 3); 352255e72915d4cbddceb435e13d81601755714e9fSE Android if (rc < 0) 353255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad; 354255e72915d4cbddceb435e13d81601755714e9fSE Android 355255e72915d4cbddceb435e13d81601755714e9fSE Android mapsize = le32_to_cpu(buf[0]); 356255e72915d4cbddceb435e13d81601755714e9fSE Android e->highbit = le32_to_cpu(buf[1]); 357255e72915d4cbddceb435e13d81601755714e9fSE Android count = le32_to_cpu(buf[2]); 358255e72915d4cbddceb435e13d81601755714e9fSE Android 359255e72915d4cbddceb435e13d81601755714e9fSE Android if (mapsize != MAPSIZE) { 360255e72915d4cbddceb435e13d81601755714e9fSE Android printf 361255e72915d4cbddceb435e13d81601755714e9fSE Android ("security: ebitmap: map size %d does not match my size %zu (high bit was %d)\n", 362255e72915d4cbddceb435e13d81601755714e9fSE Android mapsize, MAPSIZE, e->highbit); 363255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad; 364255e72915d4cbddceb435e13d81601755714e9fSE Android } 365255e72915d4cbddceb435e13d81601755714e9fSE Android if (!e->highbit) { 366255e72915d4cbddceb435e13d81601755714e9fSE Android e->node = NULL; 367255e72915d4cbddceb435e13d81601755714e9fSE Android goto ok; 368255e72915d4cbddceb435e13d81601755714e9fSE Android } 369255e72915d4cbddceb435e13d81601755714e9fSE Android if (e->highbit & (MAPSIZE - 1)) { 370255e72915d4cbddceb435e13d81601755714e9fSE Android printf 371255e72915d4cbddceb435e13d81601755714e9fSE Android ("security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)\n", 372255e72915d4cbddceb435e13d81601755714e9fSE Android e->highbit, MAPSIZE); 373255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad; 374255e72915d4cbddceb435e13d81601755714e9fSE Android } 375255e72915d4cbddceb435e13d81601755714e9fSE Android l = NULL; 376255e72915d4cbddceb435e13d81601755714e9fSE Android for (i = 0; i < count; i++) { 377255e72915d4cbddceb435e13d81601755714e9fSE Android rc = next_entry(buf, fp, sizeof(uint32_t)); 378255e72915d4cbddceb435e13d81601755714e9fSE Android if (rc < 0) { 379255e72915d4cbddceb435e13d81601755714e9fSE Android printf("security: ebitmap: truncated map\n"); 380255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad; 381255e72915d4cbddceb435e13d81601755714e9fSE Android } 382255e72915d4cbddceb435e13d81601755714e9fSE Android n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t)); 383255e72915d4cbddceb435e13d81601755714e9fSE Android if (!n) { 384255e72915d4cbddceb435e13d81601755714e9fSE Android printf("security: ebitmap: out of memory\n"); 385255e72915d4cbddceb435e13d81601755714e9fSE Android rc = -ENOMEM; 386255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad; 387255e72915d4cbddceb435e13d81601755714e9fSE Android } 388255e72915d4cbddceb435e13d81601755714e9fSE Android memset(n, 0, sizeof(ebitmap_node_t)); 389255e72915d4cbddceb435e13d81601755714e9fSE Android 390255e72915d4cbddceb435e13d81601755714e9fSE Android n->startbit = le32_to_cpu(buf[0]); 391255e72915d4cbddceb435e13d81601755714e9fSE Android 392255e72915d4cbddceb435e13d81601755714e9fSE Android if (n->startbit & (MAPSIZE - 1)) { 393255e72915d4cbddceb435e13d81601755714e9fSE Android printf 394255e72915d4cbddceb435e13d81601755714e9fSE Android ("security: ebitmap start bit (%d) is not a multiple of the map size (%zu)\n", 395255e72915d4cbddceb435e13d81601755714e9fSE Android n->startbit, MAPSIZE); 396255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad_free; 397255e72915d4cbddceb435e13d81601755714e9fSE Android } 398255e72915d4cbddceb435e13d81601755714e9fSE Android if (n->startbit > (e->highbit - MAPSIZE)) { 399255e72915d4cbddceb435e13d81601755714e9fSE Android printf 400255e72915d4cbddceb435e13d81601755714e9fSE Android ("security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)\n", 401255e72915d4cbddceb435e13d81601755714e9fSE Android n->startbit, (e->highbit - MAPSIZE)); 402255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad_free; 403255e72915d4cbddceb435e13d81601755714e9fSE Android } 404255e72915d4cbddceb435e13d81601755714e9fSE Android rc = next_entry(&map, fp, sizeof(uint64_t)); 405255e72915d4cbddceb435e13d81601755714e9fSE Android if (rc < 0) { 406255e72915d4cbddceb435e13d81601755714e9fSE Android printf("security: ebitmap: truncated map\n"); 407255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad_free; 408255e72915d4cbddceb435e13d81601755714e9fSE Android } 409255e72915d4cbddceb435e13d81601755714e9fSE Android n->map = le64_to_cpu(map); 410255e72915d4cbddceb435e13d81601755714e9fSE Android 411255e72915d4cbddceb435e13d81601755714e9fSE Android if (!n->map) { 412255e72915d4cbddceb435e13d81601755714e9fSE Android printf 413255e72915d4cbddceb435e13d81601755714e9fSE Android ("security: ebitmap: null map in ebitmap (startbit %d)\n", 414255e72915d4cbddceb435e13d81601755714e9fSE Android n->startbit); 415255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad_free; 416255e72915d4cbddceb435e13d81601755714e9fSE Android } 417255e72915d4cbddceb435e13d81601755714e9fSE Android if (l) { 418255e72915d4cbddceb435e13d81601755714e9fSE Android if (n->startbit <= l->startbit) { 419255e72915d4cbddceb435e13d81601755714e9fSE Android printf 420255e72915d4cbddceb435e13d81601755714e9fSE Android ("security: ebitmap: start bit %d comes after start bit %d\n", 421255e72915d4cbddceb435e13d81601755714e9fSE Android n->startbit, l->startbit); 422255e72915d4cbddceb435e13d81601755714e9fSE Android goto bad_free; 423255e72915d4cbddceb435e13d81601755714e9fSE Android } 424255e72915d4cbddceb435e13d81601755714e9fSE Android l->next = n; 425255e72915d4cbddceb435e13d81601755714e9fSE Android } else 426255e72915d4cbddceb435e13d81601755714e9fSE Android e->node = n; 427255e72915d4cbddceb435e13d81601755714e9fSE Android 428255e72915d4cbddceb435e13d81601755714e9fSE Android l = n; 429255e72915d4cbddceb435e13d81601755714e9fSE Android } 430255e72915d4cbddceb435e13d81601755714e9fSE Android 431255e72915d4cbddceb435e13d81601755714e9fSE Android ok: 432255e72915d4cbddceb435e13d81601755714e9fSE Android rc = 0; 433255e72915d4cbddceb435e13d81601755714e9fSE Android out: 434255e72915d4cbddceb435e13d81601755714e9fSE Android return rc; 435255e72915d4cbddceb435e13d81601755714e9fSE Android bad_free: 436255e72915d4cbddceb435e13d81601755714e9fSE Android free(n); 437255e72915d4cbddceb435e13d81601755714e9fSE Android bad: 438255e72915d4cbddceb435e13d81601755714e9fSE Android if (!rc) 439255e72915d4cbddceb435e13d81601755714e9fSE Android rc = -EINVAL; 440255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_destroy(e); 441255e72915d4cbddceb435e13d81601755714e9fSE Android goto out; 442255e72915d4cbddceb435e13d81601755714e9fSE Android} 443255e72915d4cbddceb435e13d81601755714e9fSE Android 444255e72915d4cbddceb435e13d81601755714e9fSE Android/* FLASK */ 445