/src/selinux/libsepol/src/ebitmap.c

Source

/* Author : Stephen Smalley, <stephen.smalley.work@gmail.com> */

/* FLASK */

/* 
 * Implementation of the extensible bitmap type.
 */

#include <stdlib.h>

#include <sepol/policydb/ebitmap.h>
#include <sepol/policydb/policydb.h>

#include "debug.h"
#include "private.h"

int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
{
  const ebitmap_node_t *n1, *n2;
  ebitmap_node_t *new = NULL, **prev;

  ebitmap_init(dst);

  prev = &dst->node;
  n1 = e1->node;
  n2 = e2->node;
  while (n1 || n2) {
    new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
    if (!new) {
      ebitmap_destroy(dst);
      return -ENOMEM;
    }
    if (n1 && n2 && n1->startbit == n2->startbit) {
      new->startbit = n1->startbit;
      new->map = n1->map | n2->map;
      n1 = n1->next;
      n2 = n2->next;
    } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
      new->startbit = n1->startbit;
      new->map = n1->map;
      n1 = n1->next;
    } else {
      new->startbit = n2->startbit;
      new->map = n2->map;
      n2 = n2->next;
    }

    new->next = NULL;

    *prev = new;
    prev = &new->next;
  }

  dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
  return 0;
}

int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
{
  ebitmap_t tmp;

  if (ebitmap_or(&tmp, dst, e1))
    return -1;
  ebitmap_destroy(dst);
  dst->node = tmp.node;
  dst->highbit = tmp.highbit;

  return 0;
}

int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
{
  const ebitmap_node_t *n1, *n2;
  ebitmap_node_t *new = NULL, **prev;

  ebitmap_init(dst);

  prev = &dst->node;
  n1 = e1->node;
  n2 = e2->node;
  while (n1 && n2) {
    if (n1->startbit == n2->startbit) {
      if (n1->map & n2->map) {
        new = malloc(sizeof(ebitmap_node_t));
        if (!new) {
          ebitmap_destroy(dst);
          return -ENOMEM;
        }
        new->startbit = n1->startbit;
        new->map = n1->map & n2->map;
        new->next = NULL;

        *prev = new;
        prev = &new->next;
      }

      n1 = n1->next;
      n2 = n2->next;
    } else if (n1->startbit > n2->startbit) {
      n2 = n2->next;
    } else {
      n1 = n1->next;
    }
  }

  if (new)
    dst->highbit = new->startbit + MAPSIZE;

  return 0;
}

int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
{
  const ebitmap_node_t *n1, *n2;
  ebitmap_node_t *new = NULL, **prev;
  uint32_t startbit;
  MAPTYPE map;

  ebitmap_init(dst);

  prev = &dst->node;
  n1 = e1->node;
  n2 = e2->node;
  while (n1 || n2) {
    if (n1 && n2 && n1->startbit == n2->startbit) {
      startbit = n1->startbit;
      map = n1->map ^ n2->map;
      n1 = n1->next;
      n2 = n2->next;
    } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
      startbit = n1->startbit;
      map = n1->map;
      n1 = n1->next;
    } else {
      startbit = n2->startbit;
      map = n2->map;
      n2 = n2->next;
    }

    if (map != 0) {
      new = malloc(sizeof(ebitmap_node_t));
      if (!new) {
        ebitmap_destroy(dst);
        return -ENOMEM;
      }
      new->startbit = startbit;
      new->map = map;
      new->next = NULL;

      *prev = new;
      prev = &new->next;
    }
  }

  if (new)
    dst->highbit = new->startbit + MAPSIZE;

  return 0;
}

int ebitmap_not(ebitmap_t *dst, const ebitmap_t *e1, unsigned int maxbit)
{
  const ebitmap_node_t *n;
  ebitmap_node_t *new = NULL, **prev;
  uint32_t startbit, cur_startbit;
  MAPTYPE map;

  ebitmap_init(dst);

  prev = &dst->node;
  n = e1->node;
  for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
    if (n && n->startbit == cur_startbit) {
      startbit = n->startbit;
      map = ~n->map;

      n = n->next;
    } else {
      startbit = cur_startbit;
      map = ~((MAPTYPE) 0);
    }

    if (maxbit - cur_startbit < MAPSIZE)
      map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;

    if (map != 0) {
      new = malloc(sizeof(ebitmap_node_t));
      if (!new) {
        ebitmap_destroy(dst);
        return -ENOMEM;
      }

      new->startbit = startbit;
      new->map = map;
      new->next = NULL;

      *prev = new;
      prev = &new->next;
    }
  }

  if (new)
    dst->highbit = new->startbit + MAPSIZE;

  return 0;
}

int ebitmap_andnot(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2, unsigned int maxbit)
{
  int rc;
  ebitmap_t e3;
  ebitmap_init(dst);
  rc = ebitmap_not(&e3, e2, maxbit);
  if (rc < 0)
    return rc;
  rc = ebitmap_and(dst, e1, &e3);
  ebitmap_destroy(&e3);
  if (rc < 0)
    return rc;
  return 0;
}

unsigned int ebitmap_cardinality(const ebitmap_t *e1)
{
  unsigned int count = 0;
  const ebitmap_node_t *n;

  for (n = e1->node; n; n = n->next) {
    count += __builtin_popcountll(n->map);
  }
  return count;
}

int ebitmap_hamming_distance(const ebitmap_t * e1, const ebitmap_t * e2)
{
  int rc;
  ebitmap_t tmp;
  int distance;
  if (ebitmap_cmp(e1, e2))
    return 0;
  rc = ebitmap_xor(&tmp, e1, e2);
  if (rc < 0)
    return -1;
  distance = ebitmap_cardinality(&tmp);
  ebitmap_destroy(&tmp);
  return distance;
}

int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2)
{
  const ebitmap_node_t *n1, *n2;

  if (e1->highbit != e2->highbit)
    return 0;

  n1 = e1->node;
  n2 = e2->node;
  while (n1 && n2 &&
         (n1->startbit == n2->startbit) && (n1->map == n2->map)) {
    n1 = n1->next;
    n2 = n2->next;
  }

  if (n1 || n2)
    return 0;

  return 1;
}

int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
{
  const ebitmap_node_t *n;
  ebitmap_node_t *new = NULL, **prev;

  ebitmap_init(dst);
  n = src->node;
  prev = &dst->node;
  while (n) {
    new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
    if (!new) {
      ebitmap_destroy(dst);
      return -ENOMEM;
    }
    new->startbit = n->startbit;
    new->map = n->map;
    new->next = NULL;

    *prev = new;
    prev = &new->next;

    n = n->next;
  }

  dst->highbit = src->highbit;
  return 0;
}

int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2)
{
  const ebitmap_node_t *n1, *n2;

  if (e1->highbit < e2->highbit)
    return 0;

  n1 = e1->node;
  n2 = e2->node;
  while (n1 && n2 && (n1->startbit <= n2->startbit)) {
    if (n1->startbit < n2->startbit) {
      n1 = n1->next;
      continue;
    }
    if ((n1->map & n2->map) != n2->map)
      return 0;

    n1 = n1->next;
    n2 = n2->next;
  }

  if (n2)
    return 0;

  return 1;
}

int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2)
{
  const ebitmap_node_t *n1 = e1->node;
  const ebitmap_node_t *n2 = e2->node;

  while (n1 && n2) {
    if (n1->startbit < n2->startbit) {
      n1 = n1->next;
    } else if (n2->startbit < n1->startbit) {
      n2 = n2->next;
    } else {
      if (n1->map & n2->map) {
        return 1;
      }
      n1 = n1->next;
      n2 = n2->next;
    }
  }

  return 0;
}

int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
{
  const ebitmap_node_t *n;

  if (e->highbit < bit)
    return 0;

  n = e->node;
  while (n && (n->startbit <= bit)) {
    if ((n->startbit + MAPSIZE) > bit) {
      if (n->map & (MAPBIT << (bit - n->startbit)))
        return 1;
      else
        return 0;
    }
    n = n->next;
  }

  return 0;
}

int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
{
  ebitmap_node_t *n, *prev, *new;
  uint32_t startbit = bit & ~(MAPSIZE - 1);
  uint32_t highbit = startbit + MAPSIZE;

  if (highbit == 0) {
    ERR(NULL, "bitmap overflow, bit 0x%x", bit);
    return -EINVAL;
  }

  prev = 0;
  n = e->node;
  while (n && n->startbit <= bit) {
    if ((n->startbit + MAPSIZE) > bit) {
      if (value) {
        n->map |= (MAPBIT << (bit - n->startbit));
      } else {
        n->map &= ~(MAPBIT << (bit - n->startbit));
        if (!n->map) {
          /* drop this node from the bitmap */

          if (!n->next) {
            /*
             * this was the highest map
             * within the bitmap
             */
            if (prev)
              e->highbit =
                  prev->startbit +
                  MAPSIZE;
            else
              e->highbit = 0;
          }
          if (prev)
            prev->next = n->next;
          else
            e->node = n->next;

          free(n);
        }
      }
      return 0;
    }
    prev = n;
    n = n->next;
  }

  if (!value)
    return 0;

  new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
  if (!new)
    return -ENOMEM;

  new->startbit = startbit;
  new->map = (MAPBIT << (bit - new->startbit));

  if (!n) {
    /* this node will be the highest map within the bitmap */
    e->highbit = highbit;
  }

  if (prev) {
    new->next = prev->next;
    prev->next = new;
  } else {
    new->next = e->node;
    e->node = new;
  }

  return 0;
}

int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit)
{
  ebitmap_node_t *new = NULL, **prev;
  uint32_t minstartbit = minbit & ~(MAPSIZE - 1);
  uint32_t maxstartbit = maxbit & ~(MAPSIZE - 1);
  uint32_t minhighbit = minstartbit + MAPSIZE;
  uint32_t maxhighbit = maxstartbit + MAPSIZE;
  uint32_t startbit;
  MAPTYPE mask;

  ebitmap_init(e);

  if (minbit > maxbit)
    return -EINVAL;

  if (minhighbit == 0 || maxhighbit == 0)
    return -EOVERFLOW;

  prev = &e->node;

  for (startbit = minstartbit; startbit <= maxstartbit; startbit += MAPSIZE) {
    new = malloc(sizeof(ebitmap_node_t));
    if (!new)
      return -ENOMEM;

    new->next = NULL;
    new->startbit = startbit;

    if (startbit != minstartbit && startbit != maxstartbit) {
      new->map = ~((MAPTYPE)0);
    } else if (startbit != maxstartbit) {
      new->map = ~((MAPTYPE)0) << (minbit - startbit);
    } else if (startbit != minstartbit) {
      new->map = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - startbit + 1));
    } else {
      mask = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - minbit + 1));
      new->map = (mask << (minbit - startbit));
    }

    *prev = new;
    prev = &new->next;
  }

  e->highbit = maxhighbit;

  return 0;
}

unsigned int ebitmap_highest_set_bit(const ebitmap_t * e)
{
  const ebitmap_node_t *n;
  MAPTYPE map;
  unsigned int pos = 0;

  n = e->node;
  if (!n)
    return 0;

  while (n->next)
    n = n->next;

  map = n->map;
  while (map >>= 1)
    pos++;

  return n->startbit + pos;
}

void ebitmap_destroy(ebitmap_t * e)
{
  ebitmap_node_t *n, *temp;

  if (!e)
    return;

  n = e->node;
  while (n) {
    temp = n;
    n = n->next;
    free(temp);
  }

  e->highbit = 0;
  e->node = 0;
  return;
}

int ebitmap_read(ebitmap_t * e, void *fp)
{
  int rc;
  ebitmap_node_t *n, *l;
  uint32_t buf[3], mapsize, count, i;
  uint64_t map;

  ebitmap_init(e);

  rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
  if (rc < 0)
    goto bad;

  mapsize = le32_to_cpu(buf[0]);
  e->highbit = le32_to_cpu(buf[1]);
  count = le32_to_cpu(buf[2]);

  if (mapsize != MAPSIZE) {
    ERR(NULL, "security: ebitmap: map size %d does not match my size %zu (high bit was %d)",
         mapsize, MAPSIZE, e->highbit);
    goto bad;
  }
  if (!e->highbit) {
    e->node = NULL;
    goto ok;
  }
  if (e->highbit & (MAPSIZE - 1)) {
    ERR(NULL, "security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)",
         e->highbit, MAPSIZE);
    goto bad;
  }

  if (e->highbit && !count)
    goto bad;

  l = NULL;
  for (i = 0; i < count; i++) {
    rc = next_entry(buf, fp, sizeof(uint32_t));
    if (rc < 0) {
      ERR(NULL, "security: ebitmap: truncated map");
      goto bad;
    }
    n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
    if (!n) {
      ERR(NULL, "security: ebitmap: out of memory");
      rc = -ENOMEM;
      goto bad;
    }
    memset(n, 0, sizeof(ebitmap_node_t));

    n->startbit = le32_to_cpu(buf[0]);

    if (n->startbit & (MAPSIZE - 1)) {
      ERR(NULL, "security: ebitmap start bit (%d) is not a multiple of the map size (%zu)",
           n->startbit, MAPSIZE);
      goto bad_free;
    }
    if (n->startbit > (e->highbit - MAPSIZE)) {
      ERR(NULL, "security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)",
           n->startbit, (e->highbit - MAPSIZE));
      goto bad_free;
    }
    rc = next_entry(&map, fp, sizeof(uint64_t));
    if (rc < 0) {
      ERR(NULL, "security: ebitmap: truncated map");
      goto bad_free;
    }
    n->map = le64_to_cpu(map);

    if (!n->map) {
      ERR(NULL, "security: ebitmap: null map in ebitmap (startbit %d)",
           n->startbit);
      goto bad_free;
    }
    if (l) {
      if (n->startbit <= l->startbit) {
        ERR(NULL, "security: ebitmap: start bit %d comes after start bit %d",
             n->startbit, l->startbit);
        goto bad_free;
      }
      l->next = n;
    } else
      e->node = n;

    l = n;
  }
  if (count && l->startbit + MAPSIZE != e->highbit) {
    ERR(NULL, "security: ebitmap: high bit %u has not the expected value %zu",
         e->highbit, l->startbit + MAPSIZE);
    goto bad;
  }

      ok:
  rc = 0;
      out:
  return rc;
      bad_free:
  free(n);
      bad:
  if (!rc)
    rc = -EINVAL;
  ebitmap_destroy(e);
  goto out;
}

/* FLASK */

Coverage Report

Created: 2026-01-10 06:30

Line	Count	Source
1
2		/* Author : Stephen Smalley, <stephen.smalley.work@gmail.com> */
3
4		/* FLASK */
5
6		/*
7		* Implementation of the extensible bitmap type.
8		*/
9
10		#include <stdlib.h>
11
12		#include <sepol/policydb/ebitmap.h>
13		#include <sepol/policydb/policydb.h>
14
15		#include "debug.h"
16		#include "private.h"
17
18		int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
19	1.09M	{
20	1.09M	const ebitmap_node_t n1, n2;
21	1.09M	ebitmap_node_t new = NULL, *prev;
22
23	1.09M	ebitmap_init(dst);
24
25	1.09M	prev = &dst->node;
26	1.09M	n1 = e1->node;
27	1.09M	n2 = e2->node;
28	5.02M	while (n1 \|\| n2) {
29	3.92M	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
30	3.92M	if (!new) {
31	0	ebitmap_destroy(dst);
32	0	return -ENOMEM;
33	0	}
34	3.92M	if (n1 && n2 && n1->startbit == n2->startbit) {
35	738k	new->startbit = n1->startbit;
36	738k	new->map = n1->map \| n2->map;
37	738k	n1 = n1->next;
38	738k	n2 = n2->next;
39	3.18M	} else if (!n2 \|\| (n1 && n1->startbit < n2->startbit)) {
40	378k	new->startbit = n1->startbit;
41	378k	new->map = n1->map;
42	378k	n1 = n1->next;
43	2.81M	} else {
44	2.81M	new->startbit = n2->startbit;
45	2.81M	new->map = n2->map;
46	2.81M	n2 = n2->next;
47	2.81M	}
48
49	3.92M	new->next = NULL;
50
51	3.92M	*prev = new;
52	3.92M	prev = &new->next;
53	3.92M	}
54
55	1.09M	dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
56	1.09M	return 0;
57	1.09M	}
58
59		int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
60	761k	{
61	761k	ebitmap_t tmp;
62
63	761k	if (ebitmap_or(&tmp, dst, e1))
64	0	return -1;
65	761k	ebitmap_destroy(dst);
66	761k	dst->node = tmp.node;
67	761k	dst->highbit = tmp.highbit;
68
69	761k	return 0;
70	761k	}
71
72		int ebitmap_and(ebitmap_t dst, const ebitmap_t e1, const ebitmap_t *e2)
73	1.75M	{
74	1.75M	const ebitmap_node_t n1, n2;
75	1.75M	ebitmap_node_t new = NULL, *prev;
76
77	1.75M	ebitmap_init(dst);
78
79	1.75M	prev = &dst->node;
80	1.75M	n1 = e1->node;
81	1.75M	n2 = e2->node;
82	8.70M	while (n1 && n2) {
83	6.95M	if (n1->startbit == n2->startbit) {
84	3.74M	if (n1->map & n2->map) {
85	3.29M	new = malloc(sizeof(ebitmap_node_t));
86	3.29M	if (!new) {
87	0	ebitmap_destroy(dst);
88	0	return -ENOMEM;
89	0	}
90	3.29M	new->startbit = n1->startbit;
91	3.29M	new->map = n1->map & n2->map;
92	3.29M	new->next = NULL;
93
94	3.29M	*prev = new;
95	3.29M	prev = &new->next;
96	3.29M	}
97
98	3.74M	n1 = n1->next;
99	3.74M	n2 = n2->next;
100	3.74M	} else if (n1->startbit > n2->startbit) {
101	424k	n2 = n2->next;
102	2.77M	} else {
103	2.77M	n1 = n1->next;
104	2.77M	}
105	6.95M	}
106
107	1.75M	if (new)
108	1.49M	dst->highbit = new->startbit + MAPSIZE;
109
110	1.75M	return 0;
111	1.75M	}
112
113		int ebitmap_xor(ebitmap_t dst, const ebitmap_t e1, const ebitmap_t *e2)
114	1.52k	{
115	1.52k	const ebitmap_node_t n1, n2;
116	1.52k	ebitmap_node_t new = NULL, *prev;
117	1.52k	uint32_t startbit;
118	1.52k	MAPTYPE map;
119
120	1.52k	ebitmap_init(dst);
121
122	1.52k	prev = &dst->node;
123	1.52k	n1 = e1->node;
124	1.52k	n2 = e2->node;
125	22.8k	while (n1 \|\| n2) {
126	21.3k	if (n1 && n2 && n1->startbit == n2->startbit) {
127	2.64k	startbit = n1->startbit;
128	2.64k	map = n1->map ^ n2->map;
129	2.64k	n1 = n1->next;
130	2.64k	n2 = n2->next;
131	18.7k	} else if (!n2 \|\| (n1 && n1->startbit < n2->startbit)) {
132	4.00k	startbit = n1->startbit;
133	4.00k	map = n1->map;
134	4.00k	n1 = n1->next;
135	14.6k	} else {
136	14.6k	startbit = n2->startbit;
137	14.6k	map = n2->map;
138	14.6k	n2 = n2->next;
139	14.6k	}
140
141	21.3k	if (map != 0) {
142	19.6k	new = malloc(sizeof(ebitmap_node_t));
143	19.6k	if (!new) {
144	0	ebitmap_destroy(dst);
145	0	return -ENOMEM;
146	0	}
147	19.6k	new->startbit = startbit;
148	19.6k	new->map = map;
149	19.6k	new->next = NULL;
150
151	19.6k	*prev = new;
152	19.6k	prev = &new->next;
153	19.6k	}
154	21.3k	}
155
156	1.52k	if (new)
157	1.19k	dst->highbit = new->startbit + MAPSIZE;
158
159	1.52k	return 0;
160	1.52k	}
161
162		int ebitmap_not(ebitmap_t dst, const ebitmap_t e1, unsigned int maxbit)
163	124k	{
164	124k	const ebitmap_node_t *n;
165	124k	ebitmap_node_t new = NULL, *prev;
166	124k	uint32_t startbit, cur_startbit;
167	124k	MAPTYPE map;
168
169	124k	ebitmap_init(dst);
170
171	124k	prev = &dst->node;
172	124k	n = e1->node;
173	2.01M	for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
174	1.89M	if (n && n->startbit == cur_startbit) {
175	529k	startbit = n->startbit;
176	529k	map = ~n->map;
177
178	529k	n = n->next;
179	1.36M	} else {
180	1.36M	startbit = cur_startbit;
181	1.36M	map = ~((MAPTYPE) 0);
182	1.36M	}
183
184	1.89M	if (maxbit - cur_startbit < MAPSIZE)
185	39.8k	map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;
186
187	1.89M	if (map != 0) {
188	1.53M	new = malloc(sizeof(ebitmap_node_t));
189	1.53M	if (!new) {
190	0	ebitmap_destroy(dst);
191	0	return -ENOMEM;
192	0	}
193
194	1.53M	new->startbit = startbit;
195	1.53M	new->map = map;
196	1.53M	new->next = NULL;
197
198	1.53M	*prev = new;
199	1.53M	prev = &new->next;
200	1.53M	}
201	1.89M	}
202
203	124k	if (new)
204	122k	dst->highbit = new->startbit + MAPSIZE;
205
206	124k	return 0;
207	124k	}
208
209		int ebitmap_andnot(ebitmap_t dst, const ebitmap_t e1, const ebitmap_t *e2, unsigned int maxbit)
210	83.6k	{
211	83.6k	int rc;
212	83.6k	ebitmap_t e3;
213	83.6k	ebitmap_init(dst);
214	83.6k	rc = ebitmap_not(&e3, e2, maxbit);
215	83.6k	if (rc < 0)
216	0	return rc;
217	83.6k	rc = ebitmap_and(dst, e1, &e3);
218	83.6k	ebitmap_destroy(&e3);
219	83.6k	if (rc < 0)
220	0	return rc;
221	83.6k	return 0;
222	83.6k	}
223
224		unsigned int ebitmap_cardinality(const ebitmap_t *e1)
225	908k	{
226	908k	unsigned int count = 0;
227	908k	const ebitmap_node_t *n;
228
229	3.90M	for (n = e1->node; n; n = n->next) {
230	2.99M	count += __builtin_popcountll(n->map);
231	2.99M	}
232	908k	return count;
233	908k	}
234
235		int ebitmap_hamming_distance(const ebitmap_t * e1, const ebitmap_t * e2)
236	0	{
237	0	int rc;
238	0	ebitmap_t tmp;
239	0	int distance;
240	0	if (ebitmap_cmp(e1, e2))
241	0	return 0;
242	0	rc = ebitmap_xor(&tmp, e1, e2);
243	0	if (rc < 0)
244	0	return -1;
245	0	distance = ebitmap_cardinality(&tmp);
246	0	ebitmap_destroy(&tmp);
247	0	return distance;
248	0	}
249
250		int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2)
251	23.0M	{
252	23.0M	const ebitmap_node_t n1, n2;
253
254	23.0M	if (e1->highbit != e2->highbit)
255	4.37M	return 0;
256
257	18.6M	n1 = e1->node;
258	18.6M	n2 = e2->node;
259	35.6M	while (n1 && n2 &&
260	30.0M	(n1->startbit == n2->startbit) && (n1->map == n2->map)) {
261	17.0M	n1 = n1->next;
262	17.0M	n2 = n2->next;
263	17.0M	}
264
265	18.6M	if (n1 \|\| n2)
266	13.0M	return 0;
267
268	5.61M	return 1;
269	18.6M	}
270
271		int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
272	245k	{
273	245k	const ebitmap_node_t *n;
274	245k	ebitmap_node_t new = NULL, *prev;
275
276	245k	ebitmap_init(dst);
277	245k	n = src->node;
278	245k	prev = &dst->node;
279	1.16M	while (n) {
280	923k	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
281	923k	if (!new) {
282	0	ebitmap_destroy(dst);
283	0	return -ENOMEM;
284	0	}
285	923k	new->startbit = n->startbit;
286	923k	new->map = n->map;
287	923k	new->next = NULL;
288
289	923k	*prev = new;
290	923k	prev = &new->next;
291
292	923k	n = n->next;
293	923k	}
294
295	245k	dst->highbit = src->highbit;
296	245k	return 0;
297	245k	}
298
299		int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2)
300	13.0M	{
301	13.0M	const ebitmap_node_t n1, n2;
302
303	13.0M	if (e1->highbit < e2->highbit)
304	1.41M	return 0;
305
306	11.6M	n1 = e1->node;
307	11.6M	n2 = e2->node;
308	22.0M	while (n1 && n2 && (n1->startbit <= n2->startbit)) {
309	10.5M	if (n1->startbit < n2->startbit) {
310	13.0k	n1 = n1->next;
311	13.0k	continue;
312	13.0k	}
313	10.5M	if ((n1->map & n2->map) != n2->map)
314	136k	return 0;
315
316	10.3M	n1 = n1->next;
317	10.3M	n2 = n2->next;
318	10.3M	}
319
320	11.4M	if (n2)
321	1.30M	return 0;
322
323	10.1M	return 1;
324	11.4M	}
325
326		int ebitmap_match_any(const ebitmap_t e1, const ebitmap_t e2)
327	22.9M	{
328	22.9M	const ebitmap_node_t *n1 = e1->node;
329	22.9M	const ebitmap_node_t *n2 = e2->node;
330
331	80.6M	while (n1 && n2) {
332	60.6M	if (n1->startbit < n2->startbit) {
333	36.1M	n1 = n1->next;
334	36.1M	} else if (n2->startbit < n1->startbit) {
335	16.8M	n2 = n2->next;
336	16.8M	} else {
337	7.66M	if (n1->map & n2->map) {
338	2.92M	return 1;
339	2.92M	}
340	4.74M	n1 = n1->next;
341	4.74M	n2 = n2->next;
342	4.74M	}
343	60.6M	}
344
345	19.9M	return 0;
346	22.9M	}
347
348		int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
349	23.2M	{
350	23.2M	const ebitmap_node_t *n;
351
352	23.2M	if (e->highbit < bit)
353	5.84M	return 0;
354
355	17.3M	n = e->node;
356	918M	while (n && (n->startbit <= bit)) {
357	914M	if ((n->startbit + MAPSIZE) > bit) {
358	13.0M	if (n->map & (MAPBIT << (bit - n->startbit)))
359	9.92M	return 1;
360	3.10M	else
361	3.10M	return 0;
362	13.0M	}
363	901M	n = n->next;
364	901M	}
365
366	4.35M	return 0;
367	17.3M	}
368
369		int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
370	22.3M	{
371	22.3M	ebitmap_node_t n, prev, *new;
372	22.3M	uint32_t startbit = bit & ~(MAPSIZE - 1);
373	22.3M	uint32_t highbit = startbit + MAPSIZE;
374
375	22.3M	if (highbit == 0) {
376	0	ERR(NULL, "bitmap overflow, bit 0x%x", bit);
377	0	return -EINVAL;
378	0	}
379
380	22.3M	prev = 0;
381	22.3M	n = e->node;
382	50.3M	while (n && n->startbit <= bit) {
383	42.8M	if ((n->startbit + MAPSIZE) > bit) {
384	14.8M	if (value) {
385	14.7M	n->map \|= (MAPBIT << (bit - n->startbit));
386	14.7M	} else {
387	93.7k	n->map &= ~(MAPBIT << (bit - n->startbit));
388	93.7k	if (!n->map) {
389		/* drop this node from the bitmap */
390
391	2.09k	if (!n->next) {
392		/*
393		* this was the highest map
394		* within the bitmap
395		*/
396	1.29k	if (prev)
397	1.09k	e->highbit =
398	1.09k	prev->startbit +
399	1.09k	MAPSIZE;
400	201	else
401	201	e->highbit = 0;
402	1.29k	}
403	2.09k	if (prev)
404	1.55k	prev->next = n->next;
405	539	else
406	539	e->node = n->next;
407
408	2.09k	free(n);
409	2.09k	}
410	93.7k	}
411	14.8M	return 0;
412	14.8M	}
413	27.9M	prev = n;
414	27.9M	n = n->next;
415	27.9M	}
416
417	7.48M	if (!value)
418	1.57k	return 0;
419
420	7.48M	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
421	7.48M	if (!new)
422	0	return -ENOMEM;
423
424	7.48M	new->startbit = startbit;
425	7.48M	new->map = (MAPBIT << (bit - new->startbit));
426
427	7.48M	if (!n) {
428		/* this node will be the highest map within the bitmap */
429	7.44M	e->highbit = highbit;
430	7.44M	}
431
432	7.48M	if (prev) {
433	175k	new->next = prev->next;
434	175k	prev->next = new;
435	7.31M	} else {
436	7.31M	new->next = e->node;
437	7.31M	e->node = new;
438	7.31M	}
439
440	7.48M	return 0;
441	7.48M	}
442
443		int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit)
444	39.8k	{
445	39.8k	ebitmap_node_t new = NULL, *prev;
446	39.8k	uint32_t minstartbit = minbit & ~(MAPSIZE - 1);
447	39.8k	uint32_t maxstartbit = maxbit & ~(MAPSIZE - 1);
448	39.8k	uint32_t minhighbit = minstartbit + MAPSIZE;
449	39.8k	uint32_t maxhighbit = maxstartbit + MAPSIZE;
450	39.8k	uint32_t startbit;
451	39.8k	MAPTYPE mask;
452
453	39.8k	ebitmap_init(e);
454
455	39.8k	if (minbit > maxbit)
456	517	return -EINVAL;
457
458	39.3k	if (minhighbit == 0 \|\| maxhighbit == 0)
459	22	return -EOVERFLOW;
460
461	39.2k	prev = &e->node;
462
463	360k	for (startbit = minstartbit; startbit <= maxstartbit; startbit += MAPSIZE) {
464	320k	new = malloc(sizeof(ebitmap_node_t));
465	320k	if (!new)
466	0	return -ENOMEM;
467
468	320k	new->next = NULL;
469	320k	new->startbit = startbit;
470
471	320k	if (startbit != minstartbit && startbit != maxstartbit) {
472	268k	new->map = ~((MAPTYPE)0);
473	268k	} else if (startbit != maxstartbit) {
474	13.5k	new->map = ~((MAPTYPE)0) << (minbit - startbit);
475	39.2k	} else if (startbit != minstartbit) {
476	13.5k	new->map = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - startbit + 1));
477	25.7k	} else {
478	25.7k	mask = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - minbit + 1));
479	25.7k	new->map = (mask << (minbit - startbit));
480	25.7k	}
481
482	320k	*prev = new;
483	320k	prev = &new->next;
484	320k	}
485
486	39.2k	e->highbit = maxhighbit;
487
488	39.2k	return 0;
489	39.2k	}
490
491		unsigned int ebitmap_highest_set_bit(const ebitmap_t * e)
492	89.5k	{
493	89.5k	const ebitmap_node_t *n;
494	89.5k	MAPTYPE map;
495	89.5k	unsigned int pos = 0;
496
497	89.5k	n = e->node;
498	89.5k	if (!n)
499	0	return 0;
500
501	89.5k	while (n->next)
502	0	n = n->next;
503
504	89.5k	map = n->map;
505	2.76M	while (map >>= 1)
506	2.67M	pos++;
507
508	89.5k	return n->startbit + pos;
509	89.5k	}
510
511		void ebitmap_destroy(ebitmap_t * e)
512	20.2M	{
513	20.2M	ebitmap_node_t n, temp;
514
515	20.2M	if (!e)
516	47.6k	return;
517
518	20.2M	n = e->node;
519	37.7M	while (n) {
520	17.5M	temp = n;
521	17.5M	n = n->next;
522	17.5M	free(temp);
523	17.5M	}
524
525	20.2M	e->highbit = 0;
526	20.2M	e->node = 0;
527	20.2M	return;
528	20.2M	}
529
530		int ebitmap_read(ebitmap_t * e, void *fp)
531	0	{
532	0	int rc;
533	0	ebitmap_node_t n, l;
534	0	uint32_t buf[3], mapsize, count, i;
535	0	uint64_t map;
536
537	0	ebitmap_init(e);
538
539	0	rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
540	0	if (rc < 0)
541	0	goto bad;
542
543	0	mapsize = le32_to_cpu(buf[0]);
544	0	e->highbit = le32_to_cpu(buf[1]);
545	0	count = le32_to_cpu(buf[2]);
546
547	0	if (mapsize != MAPSIZE) {
548	0	ERR(NULL, "security: ebitmap: map size %d does not match my size %zu (high bit was %d)",
549	0	mapsize, MAPSIZE, e->highbit);
550	0	goto bad;
551	0	}
552	0	if (!e->highbit) {
553	0	e->node = NULL;
554	0	goto ok;
555	0	}
556	0	if (e->highbit & (MAPSIZE - 1)) {
557	0	ERR(NULL, "security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)",
558	0	e->highbit, MAPSIZE);
559	0	goto bad;
560	0	}
561
562	0	if (e->highbit && !count)
563	0	goto bad;
564
565	0	l = NULL;
566	0	for (i = 0; i < count; i++) {
567	0	rc = next_entry(buf, fp, sizeof(uint32_t));
568	0	if (rc < 0) {
569	0	ERR(NULL, "security: ebitmap: truncated map");
570	0	goto bad;
571	0	}
572	0	n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
573	0	if (!n) {
574	0	ERR(NULL, "security: ebitmap: out of memory");
575	0	rc = -ENOMEM;
576	0	goto bad;
577	0	}
578	0	memset(n, 0, sizeof(ebitmap_node_t));
579
580	0	n->startbit = le32_to_cpu(buf[0]);
581
582	0	if (n->startbit & (MAPSIZE - 1)) {
583	0	ERR(NULL, "security: ebitmap start bit (%d) is not a multiple of the map size (%zu)",
584	0	n->startbit, MAPSIZE);
585	0	goto bad_free;
586	0	}
587	0	if (n->startbit > (e->highbit - MAPSIZE)) {
588	0	ERR(NULL, "security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)",
589	0	n->startbit, (e->highbit - MAPSIZE));
590	0	goto bad_free;
591	0	}
592	0	rc = next_entry(&map, fp, sizeof(uint64_t));
593	0	if (rc < 0) {
594	0	ERR(NULL, "security: ebitmap: truncated map");
595	0	goto bad_free;
596	0	}
597	0	n->map = le64_to_cpu(map);
598
599	0	if (!n->map) {
600	0	ERR(NULL, "security: ebitmap: null map in ebitmap (startbit %d)",
601	0	n->startbit);
602	0	goto bad_free;
603	0	}
604	0	if (l) {
605	0	if (n->startbit <= l->startbit) {
606	0	ERR(NULL, "security: ebitmap: start bit %d comes after start bit %d",
607	0	n->startbit, l->startbit);
608	0	goto bad_free;
609	0	}
610	0	l->next = n;
611	0	} else
612	0	e->node = n;
613
614	0	l = n;
615	0	}
616	0	if (count && l->startbit + MAPSIZE != e->highbit) {
617	0	ERR(NULL, "security: ebitmap: high bit %u has not the expected value %zu",
618	0	e->highbit, l->startbit + MAPSIZE);
619	0	goto bad;
620	0	}
621
622	0	ok:
623	0	rc = 0;
624	0	out:
625	0	return rc;
626	0	bad_free:
627	0	free(n);
628	0	bad:
629	0	if (!rc)
630	0	rc = -EINVAL;
631	0	ebitmap_destroy(e);
632	0	goto out;
633	0	}
634
635		/* FLASK */