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