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   systemd is free software; you can redistribute it and/or modify it
   8   under the terms of the GNU Lesser General Public License as published by
   9   the Free Software Foundation; either version 2.1 of the License, or
  10   (at your option) any later version.
  11
  12   systemd is distributed in the hope that it will be useful, but
  13   WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17   You should have received a copy of the GNU Lesser General Public License
  18   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  19 ***/
  20
  21 #include <errno.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include "macro.h"
  26 #include "uid-range.h"
  27 #include "user-util.h"
  28
  29 static bool uid_range_intersect(UidRange *range, uid_t start, uid_t nr) {
  30         assert(range);
  31
  32         return range->start <= start + nr &&
  33                 range->start + range->nr >= start;
  34 }
  35
  36 static void uid_range_coalesce(UidRange **p, unsigned *n) {
  37         unsigned i, j;
  38
  39         assert(p);
  40         assert(n);
  41
  42         for (i = 0; i < *n; i++) {
  43                 for (j = i + 1; j < *n; j++) {
  44                         UidRange *x = (*p)+i, *y = (*p)+j;
  45
  46                         if (uid_range_intersect(x, y->start, y->nr)) {
  47                                 uid_t begin, end;
  48
  49                                 begin = MIN(x->start, y->start);
  50                                 end = MAX(x->start + x->nr, y->start + y->nr);
  51
  52                                 x->start = begin;
  53                                 x->nr = end - begin;
  54
  55                                 if (*n > j+1)
  56                                         memmove(y, y+1, sizeof(UidRange) * (*n - j -1));
  57
  58                                 (*n)--;
  59                                 j--;
  60                         }
  61                 }
  62         }
  63
  64 }
  65
  66 static int uid_range_compare(const void *a, const void *b) {
  67         const UidRange *x = a, *y = b;
  68
  69         if (x->start < y->start)
  70                 return -1;
  71         if (x->start > y->start)
  72                 return 1;
  73
  74         if (x->nr < y->nr)
  75                 return -1;
  76         if (x->nr > y->nr)
  77                 return 1;
  78
  79         return 0;
  80 }
  81
  82 int uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr) {
  83         bool found = false;
  84         UidRange *x;
  85         unsigned i;
  86
  87         assert(p);
  88         assert(n);
  89
  90         if (nr <= 0)
  91                 return 0;
  92
  93         for (i = 0; i < *n; i++) {
  94                 x = (*p) + i;
  95                 if (uid_range_intersect(x, start, nr)) {
  96                         found = true;
  97                         break;
  98                 }
  99         }
 100
 101         if (found) {
 102                 uid_t begin, end;
 103
 104                 begin = MIN(x->start, start);
 105                 end = MAX(x->start + x->nr, start + nr);
 106
 107                 x->start = begin;
 108                 x->nr = end - begin;
 109         } else {
 110                 UidRange *t;
 111
 112                 t = realloc(*p, sizeof(UidRange) * (*n + 1));
 113                 if (!t)
 114                         return -ENOMEM;
 115
 116                 *p = t;
 117                 x = t + ((*n) ++);
 118
 119                 x->start = start;
 120                 x->nr = nr;
 121         }
 122
 123         qsort(*p, *n, sizeof(UidRange), uid_range_compare);
 124         uid_range_coalesce(p, n);
 125
 126         return *n;
 127 }
 128
 129 int uid_range_add_str(UidRange **p, unsigned *n, const char *s) {
 130         uid_t start, nr;
 131         const char *t;
 132         int r;
 133
 134         assert(p);
 135         assert(n);
 136         assert(s);
 137
 138         t = strchr(s, '-');
 139         if (t) {
 140                 char *b;
 141                 uid_t end;
 142
 143                 b = strndupa(s, t - s);
 144                 r = parse_uid(b, &start);
 145                 if (r < 0)
 146                         return r;
 147
 148                 r = parse_uid(t+1, &end);
 149                 if (r < 0)
 150                         return r;
 151
 152                 if (end < start)
 153                         return -EINVAL;
 154
 155                 nr = end - start + 1;
 156         } else {
 157                 r = parse_uid(s, &start);
 158                 if (r < 0)
 159                         return r;
 160
 161                 nr = 1;
 162         }
 163
 164         return uid_range_add(p, n, start, nr);
 165 }
 166
 167 int uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid) {
 168         uid_t closest = UID_INVALID, candidate;
 169         unsigned i;
 170
 171         assert(p);
 172         assert(uid);
 173
 174         candidate = *uid - 1;
 175
 176         for (i = 0; i < n; i++) {
 177                 uid_t begin, end;
 178
 179                 begin = p[i].start;
 180                 end = p[i].start + p[i].nr - 1;
 181
 182                 if (candidate >= begin && candidate <= end) {
 183                         *uid = candidate;
 184                         return 1;
 185                 }
 186
 187                 if (end < candidate)
 188                         closest = end;
 189         }
 190
 191         if (closest == UID_INVALID)
 192                 return -EBUSY;
 193
 194         *uid = closest;
 195         return 1;
 196 }
 197
 198 bool uid_range_contains(const UidRange *p, unsigned n, uid_t uid) {
 199         unsigned i;
 200
 201         assert(p);
 202         assert(uid);
 203
 204         for (i = 0; i < n; i++)
 205                 if (uid >= p[i].start && uid < p[i].start + p[i].nr)
 206                         return true;
 207
 208         return false;
 209 }