src/shared/uid-range.c

8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering/***
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  This file is part of systemd.
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  Copyright 2014 Lennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  systemd is free software; you can redistribute it and/or modify it
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  under the terms of the GNU Lesser General Public License as published by
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  the Free Software Foundation; either version 2.1 of the License, or
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  (at your option) any later version.
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  systemd is distributed in the hope that it will be useful, but
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  WITHOUT ANY WARRANTY; without even the implied warranty of
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  Lesser General Public License for more details.
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  You should have received a copy of the GNU Lesser General Public License
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering  along with systemd; If not, see <http://www.gnu.org/licenses/>.
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering***/
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
a8fbdf5424be099ba1b2b1ec261c02b8759d6b0cThomas Hindoe Paaboel Andersen#include <errno.h>
a8fbdf5424be099ba1b2b1ec261c02b8759d6b0cThomas Hindoe Paaboel Andersen#include <stdlib.h>
a8fbdf5424be099ba1b2b1ec261c02b8759d6b0cThomas Hindoe Paaboel Andersen#include <string.h>
a8fbdf5424be099ba1b2b1ec261c02b8759d6b0cThomas Hindoe Paaboel Andersen
a8fbdf5424be099ba1b2b1ec261c02b8759d6b0cThomas Hindoe Paaboel Andersen#include "macro.h"
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering#include "uid-range.h"
b1d4f8e154bf61b5de1b27461ef8e9c8c5e838a1Lennart Poettering#include "user-util.h"
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringstatic bool uid_range_intersect(UidRange *range, uid_t start, uid_t nr) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(range);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        return range->start <= start + nr &&
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                range->start + range->nr >= start;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringstatic void uid_range_coalesce(UidRange **p, unsigned *n) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        unsigned i, j;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(p);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(n);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        for (i = 0; i < *n; i++) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                for (j = i + 1; j < *n; j++) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        UidRange *x = (*p)+i, *y = (*p)+j;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        if (uid_range_intersect(x, y->start, y->nr)) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                uid_t begin, end;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                begin = MIN(x->start, y->start);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                end = MAX(x->start + x->nr, y->start + y->nr);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                x->start = begin;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                x->nr = end - begin;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                if (*n > j+1)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                        memmove(y, y+1, sizeof(UidRange) * (*n - j -1));
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                (*n) --;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                                j--;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringstatic int uid_range_compare(const void *a, const void *b) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        const UidRange *x = a, *y = b;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (x->start < y->start)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                return -1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (x->start > y->start)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                return 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (x->nr < y->nr)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                return -1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (x->nr > y->nr)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                return 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        return 0;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringint uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        bool found = false;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        UidRange *x;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        unsigned i;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(p);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(n);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (nr <= 0)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                return 0;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        for (i = 0; i < *n; i++) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                x = (*p) + i;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (uid_range_intersect(x, start, nr)) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        found = true;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        break;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (found) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                uid_t begin, end;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                begin = MIN(x->start, start);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                end = MAX(x->start + x->nr, start + nr);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                x->start = begin;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                x->nr = end - begin;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        } else {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                UidRange *t;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                t = realloc(*p, sizeof(UidRange) * (*n + 1));
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (!t)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return -ENOMEM;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                *p = t;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                x = t + ((*n) ++);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                x->start = start;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                x->nr = nr;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        qsort(*p, *n, sizeof(UidRange), uid_range_compare);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        uid_range_coalesce(p, n);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        return *n;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringint uid_range_add_str(UidRange **p, unsigned *n, const char *s) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        uid_t start, nr;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        const char *t;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        int r;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(p);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(n);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(s);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        t = strchr(s, '-');
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        if (t) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                char *b;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                uid_t end;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                b = strndupa(s, t - s);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                r = parse_uid(b, &start);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (r < 0)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return r;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                r = parse_uid(t+1, &end);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (r < 0)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return r;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (end < start)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return -EINVAL;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                nr = end - start + 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        } else {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                r = parse_uid(s, &start);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (r < 0)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return r;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                nr = 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        return uid_range_add(p, n, start, nr);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringint uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid) {
fed1e721fd0c81e60c77120539f34e16c2585634Lennart Poettering        uid_t closest = UID_INVALID, candidate;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        unsigned i;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(p);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(uid);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        candidate = *uid - 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        for (i = 0; i < n; i++) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                uid_t begin, end;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                begin = p[i].start;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                end = p[i].start + p[i].nr - 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (candidate >= begin && candidate <= end) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        *uid = candidate;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (end < candidate)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        closest = end;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        }
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
fed1e721fd0c81e60c77120539f34e16c2585634Lennart Poettering        if (closest == UID_INVALID)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                return -EBUSY;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        *uid = closest;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        return 1;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poetteringbool uid_range_contains(const UidRange *p, unsigned n, uid_t uid) {
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        unsigned i;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(p);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        assert(uid);
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        for (i = 0; i < n; i++)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                if (uid >= p[i].start && uid < p[i].start + p[i].nr)
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering                        return true;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering        return false;
8530dc4467691a893aa2e07319b18a84fec96cadLennart Poettering}