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