src/shared/uid-range.c

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