src/shared/uid-range.c

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