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