src/shared/uid-range.c

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