src/shared/uid-range.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2
   3 #include <errno.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "alloc-util.h"
   8 #include "macro.h"
   9 #include "sort-util.h"
  10 #include "uid-range.h"
  11 #include "user-util.h"
  12
  13 static bool uid_range_intersect(UidRange *range, uid_t start, uid_t nr) {
  14         assert(range);
  15
  16         return range->start <= start + nr &&
  17                 range->start + range->nr >= start;
  18 }
  19
  20 static void uid_range_coalesce(UidRange **p, unsigned *n) {
  21         assert(p);
  22         assert(n);
  23
  24         for (unsigned i = 0; i < *n; i++) {
  25                 for (unsigned j = i + 1; j < *n; j++) {
  26                         UidRange *x = (*p)+i, *y = (*p)+j;
  27
  28                         if (uid_range_intersect(x, y->start, y->nr)) {
  29                                 uid_t begin, end;
  30
  31                                 begin = MIN(x->start, y->start);
  32                                 end = MAX(x->start + x->nr, y->start + y->nr);
  33
  34                                 x->start = begin;
  35                                 x->nr = end - begin;
  36
  37                                 if (*n > j+1)
  38                                         memmove(y, y+1, sizeof(UidRange) * (*n - j -1));
  39
  40                                 (*n)--;
  41                                 j--;
  42                         }
  43                 }
  44         }
  45 }
  46
  47 static int uid_range_compare(const UidRange *a, const UidRange *b) {
  48         int r;
  49
  50         r = CMP(a->start, b->start);
  51         if (r != 0)
  52                 return r;
  53
  54         return CMP(a->nr, b->nr);
  55 }
  56
  57 int uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr) {
  58         bool found = false;
  59         UidRange *x;
  60
  61         assert(p);
  62         assert(n);
  63
  64         if (nr <= 0)
  65                 return 0;
  66
  67         for (unsigned i = 0; i < *n; i++) {
  68                 x = (*p) + i;
  69                 if (uid_range_intersect(x, start, nr)) {
  70                         found = true;
  71                         break;
  72                 }
  73         }
  74
  75         if (found) {
  76                 uid_t begin, end;
  77
  78                 begin = MIN(x->start, start);
  79                 end = MAX(x->start + x->nr, start + nr);
  80
  81                 x->start = begin;
  82                 x->nr = end - begin;
  83         } else {
  84                 UidRange *t;
  85
  86                 t = reallocarray(*p, *n + 1, sizeof(UidRange));
  87                 if (!t)
  88                         return -ENOMEM;
  89
  90                 *p = t;
  91                 x = t + ((*n) ++);
  92
  93                 x->start = start;
  94                 x->nr = nr;
  95         }
  96
  97         typesafe_qsort(*p, *n, uid_range_compare);
  98         uid_range_coalesce(p, n);
  99
 100         return *n;
 101 }
 102
 103 int uid_range_add_str(UidRange **p, unsigned *n, const char *s) {
 104         uid_t start, nr;
 105         const char *t;
 106         int r;
 107
 108         assert(p);
 109         assert(n);
 110         assert(s);
 111
 112         t = strchr(s, '-');
 113         if (t) {
 114                 char *b;
 115                 uid_t end;
 116
 117                 b = strndupa(s, t - s);
 118                 r = parse_uid(b, &start);
 119                 if (r < 0)
 120                         return r;
 121
 122                 r = parse_uid(t+1, &end);
 123                 if (r < 0)
 124                         return r;
 125
 126                 if (end < start)
 127                         return -EINVAL;
 128
 129                 nr = end - start + 1;
 130         } else {
 131                 r = parse_uid(s, &start);
 132                 if (r < 0)
 133                         return r;
 134
 135                 nr = 1;
 136         }
 137
 138         return uid_range_add(p, n, start, nr);
 139 }
 140
 141 int uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid) {
 142         uid_t closest = UID_INVALID, candidate;
 143
 144         assert(p);
 145         assert(uid);
 146
 147         candidate = *uid - 1;
 148
 149         for (unsigned i = 0; i < n; i++) {
 150                 uid_t begin, end;
 151
 152                 begin = p[i].start;
 153                 end = p[i].start + p[i].nr - 1;
 154
 155                 if (candidate >= begin && candidate <= end) {
 156                         *uid = candidate;
 157                         return 1;
 158                 }
 159
 160                 if (end < candidate)
 161                         closest = end;
 162         }
 163
 164         if (closest == UID_INVALID)
 165                 return -EBUSY;
 166
 167         *uid = closest;
 168         return 1;
 169 }
 170
 171 bool uid_range_contains(const UidRange *p, unsigned n, uid_t uid) {
 172         assert(p);
 173         assert(uid);
 174
 175         for (unsigned i = 0; i < n; i++)
 176                 if (uid >= p[i].start && uid < p[i].start + p[i].nr)
 177                         return true;
 178
 179         return false;
 180 }