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