src/shared/uid-range.c

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