Line data    Source code

       1             : /* SPDX-License-Identifier: LGPL-2.1+ */
       2             : 
       3             : #include <errno.h>
       4             : #include <stdlib.h>
       5             : #include <string.h>
       6             : 
       7             : #include "alloc-util.h"
       8             : #include "macro.h"
       9             : #include "sort-util.h"
      10             : #include "uid-range.h"
      11             : #include "user-util.h"
      12             : 
      13          15 : static bool uid_range_intersect(UidRange *range, uid_t start, uid_t nr) {
      14          15 :         assert(range);
      15             : 
      16          28 :         return range->start <= start + nr &&
      17          13 :                 range->start + range->nr >= start;
      18             : }
      19             : 
      20           7 : static void uid_range_coalesce(UidRange **p, unsigned *n) {
      21             :         unsigned i, j;
      22             : 
      23           7 :         assert(p);
      24           7 :         assert(n);
      25             : 
      26          18 :         for (i = 0; i < *n; i++) {
      27          19 :                 for (j = i + 1; j < *n; j++) {
      28           8 :                         UidRange *x = (*p)+i, *y = (*p)+j;
      29             : 
      30           8 :                         if (uid_range_intersect(x, y->start, y->nr)) {
      31             :                                 uid_t begin, end;
      32             : 
      33           3 :                                 begin = MIN(x->start, y->start);
      34           3 :                                 end = MAX(x->start + x->nr, y->start + y->nr);
      35             : 
      36           3 :                                 x->start = begin;
      37           3 :                                 x->nr = end - begin;
      38             : 
      39           3 :                                 if (*n > j+1)
      40           1 :                                         memmove(y, y+1, sizeof(UidRange) * (*n - j -1));
      41             : 
      42           3 :                                 (*n)--;
      43           3 :                                 j--;
      44             :                         }
      45             :                 }
      46             :         }
      47           7 : }
      48             : 
      49           7 : static int uid_range_compare(const UidRange *a, const UidRange *b) {
      50             :         int r;
      51             : 
      52           7 :         r = CMP(a->start, b->start);
      53           7 :         if (r != 0)
      54           7 :                 return r;
      55             : 
      56           0 :         return CMP(a->nr, b->nr);
      57             : }
      58             : 
      59           7 : int uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr) {
      60           7 :         bool found = false;
      61             :         UidRange *x;
      62             :         unsigned i;
      63             : 
      64           7 :         assert(p);
      65           7 :         assert(n);
      66             : 
      67           7 :         if (nr <= 0)
      68           0 :                 return 0;
      69             : 
      70          11 :         for (i = 0; i < *n; i++) {
      71           7 :                 x = (*p) + i;
      72           7 :                 if (uid_range_intersect(x, start, nr)) {
      73           3 :                         found = true;
      74           3 :                         break;
      75             :                 }
      76             :         }
      77             : 
      78           7 :         if (found) {
      79             :                 uid_t begin, end;
      80             : 
      81           3 :                 begin = MIN(x->start, start);
      82           3 :                 end = MAX(x->start + x->nr, start + nr);
      83             : 
      84           3 :                 x->start = begin;
      85           3 :                 x->nr = end - begin;
      86             :         } else {
      87             :                 UidRange *t;
      88             : 
      89           4 :                 t = reallocarray(*p, *n + 1, sizeof(UidRange));
      90           4 :                 if (!t)
      91           0 :                         return -ENOMEM;
      92             : 
      93           4 :                 *p = t;
      94           4 :                 x = t + ((*n) ++);
      95             : 
      96           4 :                 x->start = start;
      97           4 :                 x->nr = nr;
      98             :         }
      99             : 
     100           7 :         typesafe_qsort(*p, *n, uid_range_compare);
     101           7 :         uid_range_coalesce(p, n);
     102             : 
     103           7 :         return *n;
     104             : }
     105             : 
     106           7 : int uid_range_add_str(UidRange **p, unsigned *n, const char *s) {
     107             :         uid_t start, nr;
     108             :         const char *t;
     109             :         int r;
     110             : 
     111           7 :         assert(p);
     112           7 :         assert(n);
     113           7 :         assert(s);
     114             : 
     115           7 :         t = strchr(s, '-');
     116           7 :         if (t) {
     117             :                 char *b;
     118             :                 uid_t end;
     119             : 
     120           4 :                 b = strndupa(s, t - s);
     121           4 :                 r = parse_uid(b, &start);
     122           4 :                 if (r < 0)
     123           0 :                         return r;
     124             : 
     125           4 :                 r = parse_uid(t+1, &end);
     126           4 :                 if (r < 0)
     127           0 :                         return r;
     128             : 
     129           4 :                 if (end < start)
     130           0 :                         return -EINVAL;
     131             : 
     132           4 :                 nr = end - start + 1;
     133             :         } else {
     134           3 :                 r = parse_uid(s, &start);
     135           3 :                 if (r < 0)
     136           0 :                         return r;
     137             : 
     138           3 :                 nr = 1;
     139             :         }
     140             : 
     141           7 :         return uid_range_add(p, n, start, nr);
     142             : }
     143             : 
     144           4 : int uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid) {
     145           4 :         uid_t closest = UID_INVALID, candidate;
     146             :         unsigned i;
     147             : 
     148           4 :         assert(p);
     149           4 :         assert(uid);
     150             : 
     151           4 :         candidate = *uid - 1;
     152             : 
     153           6 :         for (i = 0; i < n; i++) {
     154             :                 uid_t begin, end;
     155             : 
     156           4 :                 begin = p[i].start;
     157           4 :                 end = p[i].start + p[i].nr - 1;
     158             : 
     159           4 :                 if (candidate >= begin && candidate <= end) {
     160           2 :                         *uid = candidate;
     161           2 :                         return 1;
     162             :                 }
     163             : 
     164           2 :                 if (end < candidate)
     165           1 :                         closest = end;
     166             :         }
     167             : 
     168           2 :         if (closest == UID_INVALID)
     169           1 :                 return -EBUSY;
     170             : 
     171           1 :         *uid = closest;
     172           1 :         return 1;
     173             : }
     174             : 
     175           4 : bool uid_range_contains(const UidRange *p, unsigned n, uid_t uid) {
     176             :         unsigned i;
     177             : 
     178           4 :         assert(p);
     179           4 :         assert(uid);
     180             : 
     181           6 :         for (i = 0; i < n; i++)
     182           4 :                 if (uid >= p[i].start && uid < p[i].start + p[i].nr)
     183           2 :                         return true;
     184             : 
     185           2 :         return false;
     186             : }