src/shared/uid-range.c

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