Coverage Report

Created: 2024-07-27 06:18

/src/selinux/libsepol/src/ebitmap.c
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 */