/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 = NULL;
  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 = NULL;
  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-10-17 06:17

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.83M	{
20	1.83M	const ebitmap_node_t n1, n2;
21	1.83M	ebitmap_node_t new = NULL, *prev;
22
23	1.83M	ebitmap_init(dst);
24
25	1.83M	prev = &dst->node;
26	1.83M	n1 = e1->node;
27	1.83M	n2 = e2->node;
28	6.82M	while (n1 \|\| n2) {
29	4.98M	new = (ebitmap_node_t *)malloc(sizeof(ebitmap_node_t));
30	4.98M	if (!new) {
31	0	ebitmap_destroy(dst);
32	0	return -ENOMEM;
33	0	}
34	4.98M	if (n1 && n2 && n1->startbit == n2->startbit) {
35	865k	new->startbit = n1->startbit;
36	865k	new->map = n1->map \| n2->map;
37	865k	n1 = n1->next;
38	865k	n2 = n2->next;
39	4.12M	} else if (!n2 \|\| (n1 && n1->startbit < n2->startbit)) {
40	635k	new->startbit = n1->startbit;
41	635k	new->map = n1->map;
42	635k	n1 = n1->next;
43	3.48M	} else {
44	3.48M	new->startbit = n2->startbit;
45	3.48M	new->map = n2->map;
46	3.48M	n2 = n2->next;
47	3.48M	}
48
49	4.98M	new->next = NULL;
50
51	4.98M	*prev = new;
52	4.98M	prev = &new->next;
53	4.98M	}
54
55	1.83M	dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
56	1.83M	return 0;
57	1.83M	}
58
59		int ebitmap_union(ebitmap_t dst, const ebitmap_t e1)
60	1.48M	{
61	1.48M	ebitmap_t tmp;
62
63	1.48M	if (ebitmap_or(&tmp, dst, e1))
64	0	return -1;
65	1.48M	ebitmap_destroy(dst);
66	1.48M	dst->node = tmp.node;
67	1.48M	dst->highbit = tmp.highbit;
68
69	1.48M	return 0;
70	1.48M	}
71
72		int ebitmap_and(ebitmap_t dst, const ebitmap_t e1, const ebitmap_t *e2)
73	3.60M	{
74	3.60M	const ebitmap_node_t n1, n2;
75	3.60M	ebitmap_node_t new = NULL, *prev;
76
77	3.60M	ebitmap_init(dst);
78
79	3.60M	prev = &dst->node;
80	3.60M	n1 = e1->node;
81	3.60M	n2 = e2->node;
82	12.4M	while (n1 && n2) {
83	8.84M	if (n1->startbit == n2->startbit) {
84	6.36M	if (n1->map & n2->map) {
85	5.15M	new = malloc(sizeof(ebitmap_node_t));
86	5.15M	if (!new) {
87	0	ebitmap_destroy(dst);
88	0	return -ENOMEM;
89	0	}
90	5.15M	new->startbit = n1->startbit;
91	5.15M	new->map = n1->map & n2->map;
92	5.15M	new->next = NULL;
93
94	5.15M	*prev = new;
95	5.15M	prev = &new->next;
96	5.15M	}
97
98	6.36M	n1 = n1->next;
99	6.36M	n2 = n2->next;
100	6.36M	} else if (n1->startbit > n2->startbit) {
101	313k	n2 = n2->next;
102	2.17M	} else {
103	2.17M	n1 = n1->next;
104	2.17M	}
105	8.84M	}
106
107	3.60M	if (new)
108	2.59M	dst->highbit = new->startbit + MAPSIZE;
109
110	3.60M	return 0;
111	3.60M	}
112
113		int ebitmap_xor(ebitmap_t dst, const ebitmap_t e1, const ebitmap_t *e2)
114	2.13k	{
115	2.13k	const ebitmap_node_t n1, n2;
116	2.13k	ebitmap_node_t new = NULL, *prev;
117	2.13k	uint32_t startbit;
118	2.13k	MAPTYPE map;
119
120	2.13k	ebitmap_init(dst);
121
122	2.13k	prev = &dst->node;
123	2.13k	n1 = e1->node;
124	2.13k	n2 = e2->node;
125	44.8k	while (n1 \|\| n2) {
126	42.7k	if (n1 && n2 && n1->startbit == n2->startbit) {
127	2.97k	startbit = n1->startbit;
128	2.97k	map = n1->map ^ n2->map;
129	2.97k	n1 = n1->next;
130	2.97k	n2 = n2->next;
131	39.7k	} else if (!n2 \|\| (n1 && n1->startbit < n2->startbit)) {
132	24.4k	startbit = n1->startbit;
133	24.4k	map = n1->map;
134	24.4k	n1 = n1->next;
135	24.4k	} else {
136	15.2k	startbit = n2->startbit;
137	15.2k	map = n2->map;
138	15.2k	n2 = n2->next;
139	15.2k	}
140
141	42.7k	if (map != 0) {
142	41.2k	new = malloc(sizeof(ebitmap_node_t));
143	41.2k	if (!new) {
144	0	ebitmap_destroy(dst);
145	0	return -ENOMEM;
146	0	}
147	41.2k	new->startbit = startbit;
148	41.2k	new->map = map;
149	41.2k	new->next = NULL;
150
151	41.2k	*prev = new;
152	41.2k	prev = &new->next;
153	41.2k	}
154	42.7k	}
155
156	2.13k	if (new)
157	1.87k	dst->highbit = new->startbit + MAPSIZE;
158
159	2.13k	return 0;
160	2.13k	}
161
162		int ebitmap_not(ebitmap_t dst, const ebitmap_t e1, unsigned int maxbit)
163	171k	{
164	171k	const ebitmap_node_t *n;
165	171k	ebitmap_node_t new = NULL, *prev;
166	171k	uint32_t startbit, cur_startbit;
167	171k	MAPTYPE map;
168
169	171k	ebitmap_init(dst);
170
171	171k	prev = &dst->node;
172	171k	n = e1->node;
173	2.19M	for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
174	2.01M	if (n && n->startbit == cur_startbit) {
175	637k	startbit = n->startbit;
176	637k	map = ~n->map;
177
178	637k	n = n->next;
179	1.38M	} else {
180	1.38M	startbit = cur_startbit;
181	1.38M	map = ~((MAPTYPE)0);
182	1.38M	}
183
184	2.01M	if (maxbit - cur_startbit < MAPSIZE)
185	37.5k	map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;
186
187	2.01M	if (map != 0) {
188	1.63M	new = malloc(sizeof(ebitmap_node_t));
189	1.63M	if (!new) {
190	0	ebitmap_destroy(dst);
191	0	return -ENOMEM;
192	0	}
193
194	1.63M	new->startbit = startbit;
195	1.63M	new->map = map;
196	1.63M	new->next = NULL;
197
198	1.63M	*prev = new;
199	1.63M	prev = &new->next;
200	1.63M	}
201	2.01M	}
202
203	171k	if (new)
204	169k	dst->highbit = new->startbit + MAPSIZE;
205
206	171k	return 0;
207	171k	}
208
209		int ebitmap_andnot(ebitmap_t dst, const ebitmap_t e1, const ebitmap_t *e2,
210		unsigned int maxbit)
211	132k	{
212	132k	int rc;
213	132k	ebitmap_t e3;
214	132k	ebitmap_init(dst);
215	132k	rc = ebitmap_not(&e3, e2, maxbit);
216	132k	if (rc < 0)
217	0	return rc;
218	132k	rc = ebitmap_and(dst, e1, &e3);
219	132k	ebitmap_destroy(&e3);
220	132k	if (rc < 0)
221	0	return rc;
222	132k	return 0;
223	132k	}
224
225		unsigned int ebitmap_cardinality(const ebitmap_t *e1)
226	2.29M	{
227	2.29M	unsigned int count = 0;
228	2.29M	const ebitmap_node_t *n;
229
230	6.38M	for (n = e1->node; n; n = n->next) {
231	4.09M	count += __builtin_popcountll(n->map);
232	4.09M	}
233	2.29M	return count;
234	2.29M	}
235
236		int ebitmap_hamming_distance(const ebitmap_t e1, const ebitmap_t e2)
237	0	{
238	0	int rc;
239	0	ebitmap_t tmp;
240	0	int distance;
241	0	if (ebitmap_cmp(e1, e2))
242	0	return 0;
243	0	rc = ebitmap_xor(&tmp, e1, e2);
244	0	if (rc < 0)
245	0	return -1;
246	0	distance = ebitmap_cardinality(&tmp);
247	0	ebitmap_destroy(&tmp);
248	0	return distance;
249	0	}
250
251		int ebitmap_cmp(const ebitmap_t e1, const ebitmap_t e2)
252	18.7M	{
253	18.7M	const ebitmap_node_t n1, n2;
254
255	18.7M	if (e1->highbit != e2->highbit)
256	2.90M	return 0;
257
258	15.8M	n1 = e1->node;
259	15.8M	n2 = e2->node;
260	46.1M	while (n1 && n2 && (n1->startbit == n2->startbit) &&
261	41.6M	(n1->map == n2->map)) {
262	30.2M	n1 = n1->next;
263	30.2M	n2 = n2->next;
264	30.2M	}
265
266	15.8M	if (n1 \|\| n2)
267	11.5M	return 0;
268
269	4.27M	return 1;
270	15.8M	}
271
272		int ebitmap_cpy(ebitmap_t dst, const ebitmap_t src)
273	397k	{
274	397k	const ebitmap_node_t *n;
275	397k	ebitmap_node_t new = NULL, *prev;
276
277	397k	ebitmap_init(dst);
278	397k	n = src->node;
279	397k	prev = &dst->node;
280	2.09M	while (n) {
281	1.69M	new = (ebitmap_node_t *)malloc(sizeof(ebitmap_node_t));
282	1.69M	if (!new) {
283	0	ebitmap_destroy(dst);
284	0	return -ENOMEM;
285	0	}
286	1.69M	new->startbit = n->startbit;
287	1.69M	new->map = n->map;
288	1.69M	new->next = NULL;
289
290	1.69M	*prev = new;
291	1.69M	prev = &new->next;
292
293	1.69M	n = n->next;
294	1.69M	}
295
296	397k	dst->highbit = src->highbit;
297	397k	return 0;
298	397k	}
299
300		int ebitmap_contains(const ebitmap_t e1, const ebitmap_t e2)
301	21.9M	{
302	21.9M	const ebitmap_node_t n1, n2;
303
304	21.9M	if (e1->highbit < e2->highbit)
305	5.90M	return 0;
306
307	16.0M	n1 = e1->node;
308	16.0M	n2 = e2->node;
309	29.0M	while (n1 && n2 && (n1->startbit <= n2->startbit)) {
310	13.2M	if (n1->startbit < n2->startbit) {
311	609k	n1 = n1->next;
312	609k	continue;
313	609k	}
314	12.6M	if ((n1->map & n2->map) != n2->map)
315	188k	return 0;
316
317	12.4M	n1 = n1->next;
318	12.4M	n2 = n2->next;
319	12.4M	}
320
321	15.8M	if (n2)
322	4.77M	return 0;
323
324	11.0M	return 1;
325	15.8M	}
326
327		int ebitmap_match_any(const ebitmap_t e1, const ebitmap_t e2)
328	19.7M	{
329	19.7M	const ebitmap_node_t *n1 = e1->node;
330	19.7M	const ebitmap_node_t *n2 = e2->node;
331
332	43.9M	while (n1 && n2) {
333	27.7M	if (n1->startbit < n2->startbit) {
334	11.7M	n1 = n1->next;
335	16.0M	} else if (n2->startbit < n1->startbit) {
336	8.39M	n2 = n2->next;
337	8.39M	} else {
338	7.65M	if (n1->map & n2->map) {
339	3.62M	return 1;
340	3.62M	}
341	4.02M	n1 = n1->next;
342	4.02M	n2 = n2->next;
343	4.02M	}
344	27.7M	}
345
346	16.1M	return 0;
347	19.7M	}
348
349		int ebitmap_get_bit(const ebitmap_t *e, unsigned int bit)
350	30.8M	{
351	30.8M	const ebitmap_node_t *n;
352
353	30.8M	if (e->highbit < bit)
354	5.76M	return 0;
355
356	25.0M	n = e->node;
357	2.39G	while (n && (n->startbit <= bit)) {
358	2.39G	if ((n->startbit + MAPSIZE) > bit) {
359	20.0M	if (n->map & (MAPBIT << (bit - n->startbit)))
360	16.3M	return 1;
361	3.70M	else
362	3.70M	return 0;
363	20.0M	}
364	2.37G	n = n->next;
365	2.37G	}
366
367	4.99M	return 0;
368	25.0M	}
369
370		int ebitmap_set_bit(ebitmap_t *e, unsigned int bit, int value)
371	22.8M	{
372	22.8M	ebitmap_node_t n, prev, *new;
373	22.8M	uint32_t startbit = bit & ~(MAPSIZE - 1);
374	22.8M	uint32_t highbit = startbit + MAPSIZE;
375
376	22.8M	if (highbit == 0) {
377	12	ERR(NULL, "bitmap overflow, bit 0x%x", bit);
378	12	return -EINVAL;
379	12	}
380
381	22.8M	prev = NULL;
382	22.8M	n = e->node;
383	457M	while (n && n->startbit <= bit) {
384	450M	if ((n->startbit + MAPSIZE) > bit) {
385	15.8M	if (value) {
386	15.7M	n->map \|= (MAPBIT << (bit - n->startbit));
387	15.7M	} else {
388	118k	n->map &= ~(MAPBIT << (bit - n->startbit));
389	118k	if (!n->map) {
390		/* drop this node from the bitmap */
391
392	4.08k	if (!n->next) {
393		/*
394		* this was the highest map
395		* within the bitmap
396		*/
397	3.16k	if (prev)
398	2.60k	e->highbit =
399	2.60k	prev->startbit +
400	2.60k	MAPSIZE;
401	562	else
402	562	e->highbit = 0;
403	3.16k	}
404	4.08k	if (prev)
405	3.37k	prev->next = n->next;
406	713	else
407	713	e->node = n->next;
408
409	4.08k	free(n);
410	4.08k	}
411	118k	}
412	15.8M	return 0;
413	15.8M	}
414	434M	prev = n;
415	434M	n = n->next;
416	434M	}
417
418	7.01M	if (!value)
419	1.88k	return 0;
420
421	7.01M	new = (ebitmap_node_t *)malloc(sizeof(ebitmap_node_t));
422	7.01M	if (!new)
423	0	return -ENOMEM;
424
425	7.01M	new->startbit = startbit;
426	7.01M	new->map = (MAPBIT << (bit - new->startbit));
427
428	7.01M	if (!n) {
429		/* this node will be the highest map within the bitmap */
430	6.96M	e->highbit = highbit;
431	6.96M	}
432
433	7.01M	if (prev) {
434	164k	new->next = prev->next;
435	164k	prev->next = new;
436	6.85M	} else {
437	6.85M	new->next = e->node;
438	6.85M	e->node = new;
439	6.85M	}
440
441	7.01M	return 0;
442	7.01M	}
443
444		int ebitmap_init_range(ebitmap_t *e, unsigned int minbit, unsigned int maxbit)
445	60.5k	{
446	60.5k	ebitmap_node_t new = NULL, *prev;
447	60.5k	uint32_t minstartbit = minbit & ~(MAPSIZE - 1);
448	60.5k	uint32_t maxstartbit = maxbit & ~(MAPSIZE - 1);
449	60.5k	uint32_t minhighbit = minstartbit + MAPSIZE;
450	60.5k	uint32_t maxhighbit = maxstartbit + MAPSIZE;
451	60.5k	uint32_t startbit;
452	60.5k	MAPTYPE mask;
453
454	60.5k	ebitmap_init(e);
455
456	60.5k	if (minbit > maxbit)
457	707	return -EINVAL;
458
459	59.8k	if (minhighbit == 0 \|\| maxhighbit == 0)
460	32	return -EOVERFLOW;
461
462	59.8k	prev = &e->node;
463
464	448k	for (startbit = minstartbit; startbit <= maxstartbit;
465	388k	startbit += MAPSIZE) {
466	388k	new = malloc(sizeof(ebitmap_node_t));
467	388k	if (!new)
468	0	return -ENOMEM;
469
470	388k	new->next = NULL;
471	388k	new->startbit = startbit;
472
473	388k	if (startbit != minstartbit && startbit != maxstartbit) {
474	314k	new->map = ~((MAPTYPE)0);
475	314k	} else if (startbit != maxstartbit) {
476	13.9k	new->map = ~((MAPTYPE)0) << (minbit - startbit);
477	59.8k	} else if (startbit != minstartbit) {
478	13.9k	new->map = ~((MAPTYPE)0) >>
479	13.9k	(MAPSIZE - (maxbit - startbit + 1));
480	45.8k	} else {
481	45.8k	mask = ~((MAPTYPE)0) >>
482	45.8k	(MAPSIZE - (maxbit - minbit + 1));
483	45.8k	new->map = (mask << (minbit - startbit));
484	45.8k	}
485
486	388k	*prev = new;
487	388k	prev = &new->next;
488	388k	}
489
490	59.8k	e->highbit = maxhighbit;
491
492	59.8k	return 0;
493	59.8k	}
494
495		unsigned int ebitmap_highest_set_bit(const ebitmap_t *e)
496	205k	{
497	205k	const ebitmap_node_t *n;
498	205k	MAPTYPE map;
499	205k	unsigned int pos = 0;
500
501	205k	n = e->node;
502	205k	if (!n)
503	1.50k	return 0;
504
505	204k	while (n->next)
506	82	n = n->next;
507
508	204k	map = n->map;
509	3.89M	while (map >>= 1)
510	3.68M	pos++;
511
512	204k	return n->startbit + pos;
513	205k	}
514
515		void ebitmap_destroy(ebitmap_t *e)
516	40.0M	{
517	40.0M	ebitmap_node_t n, temp;
518
519	40.0M	if (!e)
520	50.6k	return;
521
522	40.0M	n = e->node;
523	61.0M	while (n) {
524	20.9M	temp = n;
525	20.9M	n = n->next;
526	20.9M	free(temp);
527	20.9M	}
528
529	40.0M	e->highbit = 0;
530	40.0M	e->node = NULL;
531	40.0M	return;
532	40.0M	}
533
534		int ebitmap_read(ebitmap_t e, void fp)
535	574k	{
536	574k	int rc;
537	574k	ebitmap_node_t n, l;
538	574k	uint32_t buf[3], mapsize, count, i;
539	574k	uint64_t map;
540
541	574k	ebitmap_init(e);
542
543	574k	rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
544	574k	if (rc < 0)
545	666	goto bad;
546
547	574k	mapsize = le32_to_cpu(buf[0]);
548	574k	e->highbit = le32_to_cpu(buf[1]);
549	574k	count = le32_to_cpu(buf[2]);
550
551	574k	if (mapsize != MAPSIZE) {
552	304	ERR(NULL,
553	304	"security: ebitmap: map size %d does not match my size %zu (high bit was %d)",
554	304	mapsize, MAPSIZE, e->highbit);
555	304	goto bad;
556	304	}
557	573k	if (!e->highbit) {
558	485k	e->node = NULL;
559	485k	goto ok;
560	485k	}
561	88.5k	if (e->highbit & (MAPSIZE - 1)) {
562	36	ERR(NULL,
563	36	"security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)",
564	36	e->highbit, MAPSIZE);
565	36	goto bad;
566	36	}
567
568	88.5k	if (e->highbit && !count)
569	7	goto bad;
570
571	88.4k	l = NULL;
572	178k	for (i = 0; i < count; i++) {
573	90.1k	rc = next_entry(buf, fp, sizeof(uint32_t));
574	90.1k	if (rc < 0) {
575	271	ERR(NULL, "security: ebitmap: truncated map");
576	271	goto bad;
577	271	}
578	89.8k	n = (ebitmap_node_t *)malloc(sizeof(ebitmap_node_t));
579	89.8k	if (!n) {
580	0	ERR(NULL, "security: ebitmap: out of memory");
581	0	rc = -ENOMEM;
582	0	goto bad;
583	0	}
584	89.8k	memset(n, 0, sizeof(ebitmap_node_t));
585
586	89.8k	n->startbit = le32_to_cpu(buf[0]);
587
588	89.8k	if (n->startbit & (MAPSIZE - 1)) {
589	7	ERR(NULL,
590	7	"security: ebitmap start bit (%d) is not a multiple of the map size (%zu)",
591	7	n->startbit, MAPSIZE);
592	7	goto bad_free;
593	7	}
594	89.8k	if (n->startbit > (e->highbit - MAPSIZE)) {
595	11	ERR(NULL,
596	11	"security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)",
597	11	n->startbit, (e->highbit - MAPSIZE));
598	11	goto bad_free;
599	11	}
600	89.8k	rc = next_entry(&map, fp, sizeof(uint64_t));
601	89.8k	if (rc < 0) {
602	70	ERR(NULL, "security: ebitmap: truncated map");
603	70	goto bad_free;
604	70	}
605	89.7k	n->map = le64_to_cpu(map);
606
607	89.7k	if (!n->map) {
608	5	ERR(NULL,
609	5	"security: ebitmap: null map in ebitmap (startbit %d)",
610	5	n->startbit);
611	5	goto bad_free;
612	5	}
613	89.7k	if (l) {
614	1.47k	if (n->startbit <= l->startbit) {
615	32	ERR(NULL,
616	32	"security: ebitmap: start bit %d comes after start bit %d",
617	32	n->startbit, l->startbit);
618	32	goto bad_free;
619	32	}
620	1.44k	l->next = n;
621	1.44k	} else
622	88.3k	e->node = n;
623
624	89.7k	l = n;
625	89.7k	}
626	88.1k	if (count && l->startbit + MAPSIZE != e->highbit) {
627	79	ERR(NULL,
628	79	"security: ebitmap: high bit %u has not the expected value %zu",
629	79	e->highbit, l->startbit + MAPSIZE);
630	79	goto bad;
631	79	}
632
633	573k	ok:
634	573k	rc = 0;
635	574k	out:
636	574k	return rc;
637	125	bad_free:
638	125	free(n);
639	1.48k	bad:
640	1.48k	if (!rc)
641	481	rc = -EINVAL;
642	1.48k	ebitmap_destroy(e);
643	1.48k	goto out;
644	125	}
645
646		/* FLASK */