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

Source (jump to first uncovered line)

/* 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: 2024-07-27 06:18

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