Move user and user ID related functions to separate files.
authorAndre Noll <maan@systemlinux.org>
Thu, 6 Nov 2008 22:15:21 +0000 (23:15 +0100)
committerAndre Noll <maan@systemlinux.org>
Thu, 6 Nov 2008 22:15:21 +0000 (23:15 +0100)
Makefile
adu.c
adu.h
create.c
interactive.c
select.c
string.c
string.h
user.c [new file with mode: 0644]
user.h [new file with mode: 0644]

index 3b71004..7fed697 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-objects := adu.o string.o cmdline.o fd.o select.o create.o interactive.o select.cmdline.o format.o
+objects := adu.o string.o cmdline.o fd.o select.o create.o interactive.o select.cmdline.o format.o user.o
 all: adu
 version := 0.0.4
 
diff --git a/adu.c b/adu.c
index b3ec80e..657adb2 100644 (file)
--- a/adu.c
+++ b/adu.c
@@ -3,14 +3,13 @@
 #include <dirent.h> /* readdir() */
 #include <pwd.h>
 #include "format.h"
+#include "user.h"
+#include "select.cmdline.h"
 #include "select.h"
-
-#include "gcc-compat.h"
 #include "cmdline.h"
 #include "fd.h"
 #include "string.h"
 #include "error.h"
-#include "portable_io.h"
 
 DEFINE_ERRLIST;
 int osl_errno;
@@ -27,78 +26,11 @@ struct select_args_info select_conf;
 /** The number of different uids found so far. */
 uint32_t num_uids = 0;
 
-/** This is always a power of two. It is set in create_hash_table(). */
-static uint32_t uid_hash_table_size;
-
-/**
- * Contains info for each user that owns at least one regular file.
- *
- * Even users that are not taken into account because of the --uid
- * option occupy a slot in this hash table. This allows to find out
- * quicky whether a uid is admissible. And yes, this has to be fast.
- */
-static struct user_info *uid_hash_table;
-
-static inline int ui_used(struct user_info *ui)
-{
-       return ui->flags & UI_FL_SLOT_USED;
-}
-
-static inline int ui_admissible(struct user_info *ui)
-{
-       return ui->flags & UI_FL_ADMISSIBLE;
-}
-
 /**
  * The table containing the directory names and statistics.
  */
 struct osl_table *dir_table = NULL;
 
-/**
- * Compare the size of two directories
- *
- * \param obj1 Pointer to the first object.
- * \param obj2 Pointer to the second object.
- *
- * This function first compares the size values as usual integers. If they compare as
- * equal, the address of \a obj1 and \a obj2 are compared. So this compare function
- * returns zero if and only if \a obj1 and \a obj2 point to the same memory area.
- */
-static int size_compare(const struct osl_object *obj1, const struct osl_object *obj2)
-{
-       uint64_t d1 = *(uint64_t *)obj1->data;
-       uint64_t d2 = *(uint64_t *)obj2->data;
-       int ret = NUM_COMPARE(d2, d1);
-
-       if (ret)
-               return ret;
-       //INFO_LOG("addresses: %p, %p\n", obj1->data, obj2->data);
-       return NUM_COMPARE(obj2->data, obj1->data);
-}
-
-/**
- * Compare two osl objects pointing to unsigned integers of 64 bit size.
- *
- * \param obj1 Pointer to the first integer.
- * \param obj2 Pointer to the second integer.
- *
- * \return The values required for an osl compare function.
- *
- * \sa osl_compare_func, osl_hash_compare().
- */
-static int uint64_compare(const struct osl_object *obj1,
-               const struct osl_object *obj2)
-{
-       uint64_t d1 = read_u64((const char *)obj1->data);
-       uint64_t d2 = read_u64((const char *)obj2->data);
-
-       if (d1 < d2)
-               return 1;
-       if (d1 > d2)
-               return -1;
-       return 0;
-}
-
 static struct osl_column_description dir_table_cols[] = {
        [DT_NAME] = {
                .storage_type = OSL_MAPPED_STORAGE,
@@ -142,39 +74,6 @@ static struct osl_table_description dir_table_desc = {
        .column_descriptions = dir_table_cols,
 };
 
-/*
- * The columns of the per-user tables.
- *
- * Adu tracks disk usage on a per-user basis. For each user, a user table is
- * being created. The rows of the user table have three columns: The directory
- * number that may be resolved to the path using the directory table, the
- * number of bytes and the number of files in that directory owned by the given
- * user.
- */
-static struct osl_column_description user_table_cols[] = {
-       [UT_DIR_NUM] = {
-               .storage_type = OSL_MAPPED_STORAGE,
-               .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
-               .name = "dir_num",
-               .compare_function = uint64_compare,
-               .data_size = sizeof(uint64_t)
-       },
-       [UT_BYTES] = {
-               .storage_type = OSL_MAPPED_STORAGE,
-               .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
-               .compare_function = size_compare,
-               .name = "num_bytes",
-               .data_size = sizeof(uint64_t)
-       },
-       [UT_FILES] = {
-               .storage_type = OSL_MAPPED_STORAGE,
-               .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
-               .compare_function = size_compare,
-               .name = "num_files",
-               .data_size = sizeof(uint64_t)
-       },
-};
-
 /**
  * The log function.
  *
@@ -203,82 +102,6 @@ __printf_2_3 void __log(int ll, const char* fmt,...)
        va_end(argp);
 }
 
-static int open_user_table(struct user_info *ui, int create)
-{
-       int ret;
-       struct passwd *pw;
-
-       ui->desc = adu_malloc(sizeof(*ui->desc));
-       ui->desc->num_columns = NUM_UT_COLUMNS;
-       ui->desc->flags = 0;
-       ui->desc->column_descriptions = user_table_cols;
-       ui->desc->dir = adu_strdup(conf.database_dir_arg);
-       ui->desc->name = make_message("%u", (unsigned)ui->uid);
-       pw = getpwuid(ui->uid);
-       if (pw && pw->pw_name)
-               ui->pw_name = adu_strdup(pw->pw_name);
-
-       INFO_LOG(".............................uid #%u: %u\n",
-               (unsigned)num_uids, (unsigned)ui->uid);
-       if (create) {
-               ret = osl(osl_create_table(ui->desc));
-               if (ret < 0)
-                       goto err;
-               num_uids++;
-       }
-       ret = osl(osl_open_table(ui->desc, &ui->table));
-       if (ret < 0)
-               goto err;
-       return 1;
-err:
-       free((char *)ui->desc->name);
-       free((char *)ui->desc->dir);
-       free(ui->pw_name);
-       free(ui->desc);
-       ui->desc->name = NULL;
-       ui->desc->dir = NULL;
-       ui->desc = NULL;
-       ui->table = NULL;
-       ui->flags = 0;
-       return ret;
-}
-
-int for_each_admissible_user(int (*func)(struct user_info *, void *),
-               void *data)
-{
-       struct user_info *ui = uid_hash_table;
-
-       if (!ui)
-               return -ERRNO_TO_ERROR(EFAULT);
-
-       for (; ui < uid_hash_table + uid_hash_table_size; ui++) {
-               int ret;
-
-               if (!ui_used(ui) || !ui_admissible(ui))
-                       continue;
-               ret = func(ui, data);
-               if (ret < 0)
-                       return ret;
-       }
-       return 1;
-}
-
-#define PRIME1 0xb11924e1
-#define PRIME2 0x01000193
-
-void create_hash_table(unsigned bits)
-{
-       uid_hash_table_size = 1 << bits;
-       uid_hash_table = adu_calloc(uid_hash_table_size *
-               sizeof(struct user_info));
-}
-
-static void free_hash_table(void)
-{
-       free(uid_hash_table);
-       uid_hash_table = NULL;
-}
-
 static void close_dir_table(void)
 {
        int ret;
@@ -292,32 +115,6 @@ static void close_dir_table(void)
        dir_table = NULL;
 }
 
-static int close_user_table(struct user_info *ui, __a_unused void *data)
-{
-       int ret;
-
-       ret = osl(osl_close_table(ui->table, OSL_MARK_CLEAN));
-       if (ret < 0)
-               ERROR_LOG("failed to close user table %u: %s\n",
-                       (unsigned) ui->uid, adu_strerror(-ret));
-       free((char *)ui->desc->name);
-       ui->desc->name = NULL;
-       free((char *)ui->desc->dir);
-       ui->desc->dir = NULL;
-       free(ui->pw_name);
-       ui->pw_name = NULL;
-       free(ui->desc);
-       ui->desc = NULL;
-       ui->table = NULL;
-       ui->flags = 0;
-       return 1;
-}
-
-static void close_user_tables(void)
-{
-       for_each_admissible_user(close_user_table, NULL);
-}
-
 void close_all_tables(void)
 {
        close_dir_table();
@@ -350,90 +147,6 @@ static int init_signals(void)
        return 1;
 }
 
-/*
- * We use a hash table of size s=2^uid_hash_bits to map the uids into the
- * interval [0..s]. Hash collisions are treated by open addressing, i.e.
- * unused slots in the table are used to store different uids that hash to the
- * same slot.
- *
- * If a hash collision occurs, different slots are successively probed in order
- * to find an unused slot for the new uid. Probing is implemented via a second
- * hash function that maps the uid to h=(uid * PRIME2) | 1, which is always an
- * odd number.
- *
- * An odd number is sufficient to make sure each entry of the hash table gets
- * probed for probe_num between 0 and s-1 because s is a power of two, hence
- * the second hash value has never a common divisor with the hash table size.
- * IOW: h is invertible in the ring [0..s].
- */
-static uint32_t double_hash(uint32_t uid, uint32_t probe_num)
-{
-       return (uid * PRIME1 + ((uid * PRIME2) | 1) * probe_num)
-               % uid_hash_table_size;
-}
-
-static int uid_is_admissible(uint32_t uid, struct uid_range *urs)
-{
-       struct uid_range *ur;
-       int ret = 1;
-
-       if (!urs) /* empty array means all uids are allowed */
-               return 1;
-       FOR_EACH_UID_RANGE(ur, urs)
-               if (ur->low <= uid && ur->high >= uid)
-                       goto out;
-       ret = 0;
-out:
-       DEBUG_LOG("uid %u is %sadmissible\n", (unsigned)uid,
-               ret? "" : "not ");
-       return ret;
-}
-
-int search_uid(uint32_t uid, struct uid_range *urs,
-               enum search_uid_flags flags, struct user_info **ui_ptr)
-{
-       uint32_t p;
-
-       for (p = 0; p < uid_hash_table_size; p++) {
-               struct user_info *ui = uid_hash_table + double_hash(uid, p);
-
-               if (!ui_used(ui)) {
-                       int ret;
-                       if (!flags)
-                               return -E_BAD_UID;
-                       ui->uid = uid;
-                       ui->flags |= UI_FL_SLOT_USED;
-                       if (!uid_is_admissible(uid, urs))
-                               return 0;
-                       ui->flags |= UI_FL_ADMISSIBLE;
-                       ret = open_user_table(ui, flags & CREATE_USER_TABLE);
-                       if (ret < 0)
-                               return ret;
-
-                       if (ui_ptr)
-                               *ui_ptr = ui;
-                       return 1;
-               }
-               if (ui->uid != uid)
-                       continue;
-               if (ui_ptr)
-                       *ui_ptr = ui;
-               return 0;
-       }
-       return flags? -E_HASH_TABLE_OVERFLOW : -E_BAD_UID;
-}
-
-char *get_uid_list_name(void)
-{
-       return make_message("%s/uid_list", conf.database_dir_arg);
-}
-
-void sort_hash_table(int (*comp)(const void *, const void *))
-{
-       qsort(uid_hash_table, uid_hash_table_size, sizeof(struct user_info),
-               comp);
-}
-
 int open_dir_table(int create)
 {
        dir_table_desc.dir = adu_strdup(conf.database_dir_arg);
diff --git a/adu.h b/adu.h
index b9e6ee9..509c0a2 100644 (file)
--- a/adu.h
+++ b/adu.h
@@ -21,7 +21,7 @@
 #include <assert.h>
 #include <osl.h>
 #include "gcc-compat.h"
-#include "select.cmdline.h"
+#include "portable_io.h"
 
 /** debug loglevel, gets really noisy */
 #define DEBUG 1
@@ -134,66 +134,6 @@ enum dir_table_columns {
        NUM_DT_COLUMNS
 };
 
-/** The columns of the id table. */
-enum user_table_columns {
-       /** The numer of the directory. */
-       UT_DIR_NUM,
-       /** The number of bytes of all regular files in this dir owned by this id. */
-       UT_BYTES,
-       /** The number of files in this dir owned by this id. */
-       UT_FILES,
-       /** Number of columns in this table. */
-       NUM_UT_COLUMNS
-};
-
-/** Flags for the user hash table. */
-enum uid_info_flags {
-       /** Whether this slot of the hash table is used. */
-       UI_FL_SLOT_USED = 1,
-       /** Whether this uid should be taken into account. */
-       UI_FL_ADMISSIBLE = 2,
-};
-
-/** Information about one admissible user. */
-struct user_info {
-       /** User ID. */
-       uint32_t uid;
-       /** \sa enum uid_info_flags. */
-       uint32_t flags;
-       /** The user name.  */
-       char *pw_name;
-       /** The user table of this user.*/
-       struct osl_table *table;
-       /** Total number of files owned by this user. */
-       uint64_t files;
-       /** Total number of bytes owned by this user. */
-       uint64_t bytes;
-       /** Total number of directories that contain at least one file */
-       uint64_t dirs;
-       /** The description of the user table. */
-       struct osl_table_description *desc;
-};
-
-/**
- * Describes one range of admissible user IDs.
- *
- * adu converts the admissible user ids given at the command line
- * into an array of such structs.
- */
-struct uid_range {
-       /** Lowest admissible user ID. */
-       uint32_t low;
-       /** Greatest admissible user ID. */
-       uint32_t high;
-};
-
-enum search_uid_flags {
-       OPEN_USER_TABLE = 1,
-       CREATE_USER_TABLE = 2,
-};
-
-#define FOR_EACH_UID_RANGE(ur, urs) for (ur = urs; ur->low <= ur->high; ur++)
-
 extern uint32_t num_uids;
 extern struct osl_table *dir_table;
 
@@ -208,19 +148,56 @@ extern struct gengetopt_args_info conf;
  */
 extern struct select_args_info select_conf;
 
+/**
+ * Compare two osl objects pointing to unsigned integers of 64 bit size.
+ *
+ * \param obj1 Pointer to the first integer.
+ * \param obj2 Pointer to the second integer.
+ *
+ * \return The values required for an osl compare function.
+ *
+ * \sa osl_compare_func, osl_hash_compare().
+ */
+static inline int uint64_compare(const struct osl_object *obj1,
+               const struct osl_object *obj2)
+{
+       uint64_t d1 = read_u64((const char *)obj1->data);
+       uint64_t d2 = read_u64((const char *)obj2->data);
+
+       if (d1 < d2)
+               return 1;
+       if (d1 > d2)
+               return -1;
+       return 0;
+}
+
+/**
+ * Compare the size of two directories
+ *
+ * \param obj1 Pointer to the first object.
+ * \param obj2 Pointer to the second object.
+ *
+ * This function first compares the size values as usual integers. If they compare as
+ * equal, the address of \a obj1 and \a obj2 are compared. So this compare function
+ * returns zero if and only if \a obj1 and \a obj2 point to the same memory area.
+ */
+static inline int size_compare(const struct osl_object *obj1, const struct osl_object *obj2)
+{
+       uint64_t d1 = *(uint64_t *)obj1->data;
+       uint64_t d2 = *(uint64_t *)obj2->data;
+       int ret = NUM_COMPARE(d2, d1);
+
+       if (ret)
+               return ret;
+       //INFO_LOG("addresses: %p, %p\n", obj1->data, obj2->data);
+       return NUM_COMPARE(obj2->data, obj1->data);
+}
+
 /* adu.c */
 __printf_2_3 void __log(int, const char*, ...);
 int open_dir_table(int create);
 void check_signals(void);
 void close_all_tables(void);
-char *get_uid_list_name(void);
-void create_hash_table(unsigned bits);
-int search_uid(uint32_t uid, struct uid_range *urs,
-               enum search_uid_flags flags, struct user_info **ui_ptr);
-int for_each_admissible_user(int (*func)(struct user_info *, void *),
-               void *data);
-void sort_hash_table(int (*comp)(const void *, const void *));
-
 /* create.c */
 int com_create(void);
 
index 022129b..d08da1c 100644 (file)
--- a/create.c
+++ b/create.c
 #include "fd.h"
 #include "string.h"
 #include "error.h"
-#include "portable_io.h"
+#include "user.h"
 
 /* Id of the device containing the base dir. */
 static dev_t device_id;
 
-static int write_uid(struct user_info *ui, void *data)
-{
-       char **p = data;
-
-       write_u32(*p, ui->uid);
-       *p += sizeof(uint32_t);
-       return 1;
-}
-
-static int write_uid_list(void)
-{
-       char *buf, *p, *filename;
-       size_t size = num_uids * sizeof(uint32_t);
-       int ret;
-
-       if (!num_uids)
-               return 0;
-       buf = p = adu_malloc(size);
-       ret = for_each_admissible_user(write_uid, &p);
-       if (ret < 0)
-               goto out;
-       filename = get_uid_list_name();
-       ret = adu_write_file(filename, buf, size);
-       free(filename);
-out:
-       free(buf);
-       return ret;
-}
-
 static int add_directory(char *dirname, uint64_t *dir_num, uint64_t *parent_dir_num,
                uint64_t *dir_size, uint64_t *dir_files)
 {
@@ -201,7 +172,7 @@ int com_create(void)
        ret = scan_dir(conf.base_dir_arg, &zero);
        if (ret < 0)
                goto out;
-       ret = write_uid_list();
+       ret = write_uid_file();
 out:
        close_all_tables();
        return ret;
index b325415..9460877 100644 (file)
@@ -2,10 +2,11 @@
 
 #include "adu.h"
 #include "format.h"
-#include "select.h"
+#include "user.h"
 #include "string.h"
+#include "select.cmdline.h"
+#include "select.h"
 #include "error.h"
-#include "cmdline.h"
 
 /**
  * Describes one valid command for interactive mode.
index c26b548..46b5372 100644 (file)
--- a/select.c
+++ b/select.c
@@ -14,7 +14,8 @@
 #include "fd.h"
 #include "string.h"
 #include "error.h"
-#include "portable_io.h"
+#include "user.h"
+#include "select.cmdline.h"
 
 /* global list */
 #define GLOBAL_LIST_ATOMS \
@@ -585,41 +586,6 @@ static int print_statistics(struct format_info *fi)
        return -ERRNO_TO_ERROR(-EINVAL);
 }
 
-static int read_uid_file(struct uid_range *admissible_uids)
-{
-       size_t size;
-       uint32_t n;
-       char *filename = get_uid_list_name(), *map;
-       int ret = mmap_full_file(filename, O_RDONLY, (void **)&map, &size, NULL);
-       unsigned bits;
-
-       if (ret < 0) {
-               INFO_LOG("failed to map %s\n", filename);
-               free(filename);
-               return ret;
-       }
-       num_uids = size / 4;
-       INFO_LOG("found %u uids in %s\n", (unsigned)num_uids, filename);
-       free(filename);
-       /*
-        * Compute number of hash table bits. The hash table size must be a
-        * power of two and larger than the number of uids.
-        */
-       bits = 2;
-       while (1 << bits < num_uids)
-               bits++;
-       create_hash_table(bits);
-       for (n = 0; n < num_uids; n++) {
-               uint32_t uid = read_u32(map + n * sizeof(uid));
-               ret = search_uid(uid, admissible_uids, OPEN_USER_TABLE, NULL);
-               if (ret < 0)
-                       goto out;
-       }
-out:
-       adu_munmap(map, size);
-       return ret;
-}
-
 int run_select_query(struct uid_range *admissible_uids, struct format_info *fi)
 {
        int ret;
index a219bef..aec62ae 100644 (file)
--- a/string.c
+++ b/string.c
@@ -245,92 +245,6 @@ __must_check unsigned split_args(char *args, char *** const argv_ptr, const char
        return n;
 }
 
-static int check_uid_arg(const char *arg, uint32_t *uid)
-{
-       const uint32_t max = ~0U;
-       /*
-        * we need an 64-bit int for string -> uid conversion because strtoll()
-        * returns a signed value.
-        */
-       int64_t val;
-       int ret = atoi64(arg, &val);
-
-       if (ret < 0)
-               return ret;
-       if (val < 0 || val > max)
-               return -ERRNO_TO_ERROR(EINVAL);
-       *uid = val;
-       return 1;
-}
-
-int parse_uid_range(const char *orig_arg, struct uid_range *ur)
-{
-       int ret;
-       char *arg = adu_strdup(orig_arg), *p = strchr(arg, '-');
-
-       if (!p || p == arg) { /* -42 or 42 */
-               ret = check_uid_arg(p? p + 1 : arg, &ur->high);
-               if (ret < 0)
-                       goto out;
-               ur->low = p? 0 : ur->high;
-               ret = 1;
-               goto out;
-       }
-       /* 42- or 42-4711 */
-       *p = '\0';
-       p++;
-       ret = check_uid_arg(arg, &ur->low);
-       if (ret < 0)
-               goto out;
-       ur->high = ~0U;
-       if (*p) { /* 42-4711 */
-               ret = check_uid_arg(p, &ur->high);
-               if (ret < 0)
-                       goto out;
-       }
-       if (ur->low > ur->high)
-               ret = -ERRNO_TO_ERROR(EINVAL);
-out:
-       if (ret < 0)
-               ERROR_LOG("bad uid option: %s\n", orig_arg);
-       else
-               INFO_LOG("admissible uid range: %u - %u\n", ur->low,
-                       ur->high);
-       free(arg);
-       return ret;
-}
-
-int parse_uid_arg(const char *orig_arg, struct uid_range **ur)
-{
-       char *arg, **argv;
-       unsigned n;
-       int i, ret = 1;
-
-       if (!orig_arg)
-               return 0;
-       arg = adu_strdup(orig_arg);
-       n = split_args(arg, &argv, ",");
-       if (!n)
-               return -E_SYNTAX;
-       *ur = adu_malloc((n + 1) * sizeof(struct uid_range));
-       for (i = 0; i < n; i++) {
-               ret = parse_uid_range(argv[i], *ur + i);
-               if (ret < 0)
-                       break;
-       }
-       free(argv);
-       free(arg);
-       if (ret < 0) {
-               free(*ur);
-               *ur = NULL;
-               return ret;
-       }
-       /* an empty range indicates the end of the list */
-       (*ur)[n].low = 1;
-       (*ur)[n].high = 0;
-       return n;
-}
-
 enum line_state_flags {LSF_HAVE_WORD = 1, LSF_BACKSLASH = 2, LSF_QUOTE = 4};
 
 static int get_next_word(const char *line, char **word)
index 37c7cd8..1eb8f01 100644 (file)
--- a/string.h
+++ b/string.h
@@ -13,6 +13,6 @@ __must_check __malloc char *adu_strdup(const char *s);
 __must_check __malloc char *adu_strcat(char *a, const char *b);
 __must_check __malloc __printf_1_2 char *make_message(const char *fmt, ...);
 __must_check int atoi64(const char *str, int64_t *result);
-int parse_uid_arg(const char *orig_arg, struct uid_range **ur);
+__must_check unsigned split_args(char *args, char *** const argv_ptr, const char *delim);
 int create_argv(const char *line, char ***result);
 void free_argv(char **argv);
diff --git a/user.c b/user.c
new file mode 100644 (file)
index 0000000..233764f
--- /dev/null
+++ b/user.c
@@ -0,0 +1,431 @@
+/*
+ * Copyright (C) 2008 Andre Noll <maan@systemlinux.org>
+ *
+ * Licensed under the GPL v2. For licencing details see COPYING.
+ */
+
+/** \file user.c uid User and user ID handling. */
+
+#include "adu.h"
+#include <dirent.h> /* readdir() */
+#include <sys/types.h>
+#include <pwd.h>
+#include "cmdline.h" /* TODO: This file should be independent of command line options */
+#include "user.h"
+#include "fd.h"
+#include "string.h"
+#include "error.h"
+
+/**
+ * Describes one range of admissible user IDs.
+ *
+ * adu converts the admissible user ids given at the command line
+ * into an array of such structs.
+ */
+struct uid_range {
+       /** Lowest admissible user ID. */
+       uint32_t low;
+       /** Greatest admissible user ID. */
+       uint32_t high;
+};
+
+#define FOR_EACH_UID_RANGE(ur, urs) for (ur = urs; ur->low <= ur->high; ur++)
+
+/** Flags for the user hash table. */
+enum uid_info_flags {
+       /** Whether this slot of the hash table is used. */
+       UI_FL_SLOT_USED = 1,
+       /** Whether this uid should be taken into account. */
+       UI_FL_ADMISSIBLE = 2,
+};
+/*
+ * Contains info for each user that owns at least one regular file.
+ *
+ * Even users that are not taken into account because of the --uid
+ * option occupy a slot in this hash table. This allows to find out
+ * quicky whether a uid is admissible. And yes, this has to be fast.
+ */
+static struct user_info *uid_hash_table;
+
+/** This is always a power of two. It is set in create_hash_table(). */
+static uint32_t uid_hash_table_size;
+
+/*
+ * The columns of the per-user tables.
+ *
+ * Adu tracks disk usage on a per-user basis. For each user, a user table is
+ * being created. The rows of the user table have three columns: The directory
+ * number that may be resolved to the path using the directory table, the
+ * number of bytes and the number of files in that directory owned by the given
+ * user.
+ */
+static struct osl_column_description user_table_cols[] = {
+       [UT_DIR_NUM] = {
+               .storage_type = OSL_MAPPED_STORAGE,
+               .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
+               .name = "dir_num",
+               .compare_function = uint64_compare,
+               .data_size = sizeof(uint64_t)
+       },
+       [UT_BYTES] = {
+               .storage_type = OSL_MAPPED_STORAGE,
+               .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
+               .compare_function = size_compare,
+               .name = "num_bytes",
+               .data_size = sizeof(uint64_t)
+       },
+       [UT_FILES] = {
+               .storage_type = OSL_MAPPED_STORAGE,
+               .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
+               .compare_function = size_compare,
+               .name = "num_files",
+               .data_size = sizeof(uint64_t)
+       },
+};
+
+static int check_uid_arg(const char *arg, uint32_t *uid)
+{
+       const uint32_t max = ~0U;
+       /*
+        * we need an 64-bit int for string -> uid conversion because strtoll()
+        * returns a signed value.
+        */
+       int64_t val;
+       int ret = atoi64(arg, &val);
+
+       if (ret < 0)
+               return ret;
+       if (val < 0 || val > max)
+               return -ERRNO_TO_ERROR(EINVAL);
+       *uid = val;
+       return 1;
+}
+
+static int parse_uid_range(const char *orig_arg, struct uid_range *ur)
+{
+       int ret;
+       char *arg = adu_strdup(orig_arg), *p = strchr(arg, '-');
+
+       if (!p || p == arg) { /* -42 or 42 */
+               ret = check_uid_arg(p? p + 1 : arg, &ur->high);
+               if (ret < 0)
+                       goto out;
+               ur->low = p? 0 : ur->high;
+               ret = 1;
+               goto out;
+       }
+       /* 42- or 42-4711 */
+       *p = '\0';
+       p++;
+       ret = check_uid_arg(arg, &ur->low);
+       if (ret < 0)
+               goto out;
+       ur->high = ~0U;
+       if (*p) { /* 42-4711 */
+               ret = check_uid_arg(p, &ur->high);
+               if (ret < 0)
+                       goto out;
+       }
+       if (ur->low > ur->high)
+               ret = -ERRNO_TO_ERROR(EINVAL);
+out:
+       if (ret < 0)
+               ERROR_LOG("bad uid option: %s\n", orig_arg);
+       else
+               INFO_LOG("admissible uid range: %u - %u\n", ur->low,
+                       ur->high);
+       free(arg);
+       return ret;
+}
+
+int parse_uid_arg(const char *orig_arg, struct uid_range **ur)
+{
+       char *arg, **argv;
+       unsigned n;
+       int i, ret = 1;
+
+       if (!orig_arg)
+               return 0;
+       arg = adu_strdup(orig_arg);
+       n = split_args(arg, &argv, ",");
+       if (!n)
+               return -E_SYNTAX;
+       *ur = adu_malloc((n + 1) * sizeof(struct uid_range));
+       for (i = 0; i < n; i++) {
+               ret = parse_uid_range(argv[i], *ur + i);
+               if (ret < 0)
+                       break;
+       }
+       free(argv);
+       free(arg);
+       if (ret < 0) {
+               free(*ur);
+               *ur = NULL;
+               return ret;
+       }
+       /* an empty range indicates the end of the list */
+       (*ur)[n].low = 1;
+       (*ur)[n].high = 0;
+       return n;
+}
+
+
+static inline int ui_used(struct user_info *ui)
+{
+       return ui->flags & UI_FL_SLOT_USED;
+}
+
+static inline int ui_admissible(struct user_info *ui)
+{
+       return ui->flags & UI_FL_ADMISSIBLE;
+}
+
+static int open_user_table(struct user_info *ui, int create)
+{
+       int ret;
+       struct passwd *pw;
+
+       ui->desc = adu_malloc(sizeof(*ui->desc));
+       ui->desc->num_columns = NUM_UT_COLUMNS;
+       ui->desc->flags = 0;
+       ui->desc->column_descriptions = user_table_cols;
+       ui->desc->dir = adu_strdup(conf.database_dir_arg);
+       ui->desc->name = make_message("%u", (unsigned)ui->uid);
+       pw = getpwuid(ui->uid);
+       if (pw && pw->pw_name)
+               ui->pw_name = adu_strdup(pw->pw_name);
+
+       INFO_LOG(".............................uid #%u: %u\n",
+               (unsigned)num_uids, (unsigned)ui->uid);
+       if (create) {
+               ret = osl(osl_create_table(ui->desc));
+               if (ret < 0)
+                       goto err;
+               num_uids++;
+       }
+       ret = osl(osl_open_table(ui->desc, &ui->table));
+       if (ret < 0)
+               goto err;
+       return 1;
+err:
+       free((char *)ui->desc->name);
+       free((char *)ui->desc->dir);
+       free(ui->pw_name);
+       free(ui->desc);
+       ui->desc->name = NULL;
+       ui->desc->dir = NULL;
+       ui->desc = NULL;
+       ui->table = NULL;
+       ui->flags = 0;
+       return ret;
+}
+
+int for_each_admissible_user(int (*func)(struct user_info *, void *),
+               void *data)
+{
+       struct user_info *ui = uid_hash_table;
+
+       if (!ui)
+               return -ERRNO_TO_ERROR(EFAULT);
+
+       for (; ui < uid_hash_table + uid_hash_table_size; ui++) {
+               int ret;
+
+               if (!ui_used(ui) || !ui_admissible(ui))
+                       continue;
+               ret = func(ui, data);
+               if (ret < 0)
+                       return ret;
+       }
+       return 1;
+}
+
+#define PRIME1 0xb11924e1
+#define PRIME2 0x01000193
+
+void create_hash_table(unsigned bits)
+{
+       uid_hash_table_size = 1 << bits;
+       uid_hash_table = adu_calloc(uid_hash_table_size *
+               sizeof(struct user_info));
+}
+
+void free_hash_table(void)
+{
+       free(uid_hash_table);
+       uid_hash_table = NULL;
+}
+
+static int close_user_table(struct user_info *ui, __a_unused void *data)
+{
+       int ret;
+
+       ret = osl(osl_close_table(ui->table, OSL_MARK_CLEAN));
+       if (ret < 0)
+               ERROR_LOG("failed to close user table %u: %s\n",
+                       (unsigned) ui->uid, adu_strerror(-ret));
+       free((char *)ui->desc->name);
+       ui->desc->name = NULL;
+       free((char *)ui->desc->dir);
+       ui->desc->dir = NULL;
+       free(ui->pw_name);
+       ui->pw_name = NULL;
+       free(ui->desc);
+       ui->desc = NULL;
+       ui->table = NULL;
+       ui->flags = 0;
+       return 1;
+}
+
+void close_user_tables(void)
+{
+       for_each_admissible_user(close_user_table, NULL);
+}
+
+/*
+ * We use a hash table of size s=2^uid_hash_bits to map the uids into the
+ * interval [0..s]. Hash collisions are treated by open addressing, i.e.
+ * unused slots in the table are used to store different uids that hash to the
+ * same slot.
+ *
+ * If a hash collision occurs, different slots are successively probed in order
+ * to find an unused slot for the new uid. Probing is implemented via a second
+ * hash function that maps the uid to h=(uid * PRIME2) | 1, which is always an
+ * odd number.
+ *
+ * An odd number is sufficient to make sure each entry of the hash table gets
+ * probed for probe_num between 0 and s-1 because s is a power of two, hence
+ * the second hash value has never a common divisor with the hash table size.
+ * IOW: h is invertible in the ring [0..s].
+ */
+static uint32_t double_hash(uint32_t uid, uint32_t probe_num)
+{
+       return (uid * PRIME1 + ((uid * PRIME2) | 1) * probe_num)
+               % uid_hash_table_size;
+}
+
+static int uid_is_admissible(uint32_t uid, struct uid_range *urs)
+{
+       struct uid_range *ur;
+       int ret = 1;
+
+       if (!urs) /* empty array means all uids are allowed */
+               return 1;
+       FOR_EACH_UID_RANGE(ur, urs)
+               if (ur->low <= uid && ur->high >= uid)
+                       goto out;
+       ret = 0;
+out:
+       DEBUG_LOG("uid %u is %sadmissible\n", (unsigned)uid,
+               ret? "" : "not ");
+       return ret;
+}
+
+int search_uid(uint32_t uid, struct uid_range *urs,
+               enum search_uid_flags flags, struct user_info **ui_ptr)
+{
+       uint32_t p;
+
+       for (p = 0; p < uid_hash_table_size; p++) {
+               struct user_info *ui = uid_hash_table + double_hash(uid, p);
+
+               if (!ui_used(ui)) {
+                       int ret;
+                       if (!flags)
+                               return -E_BAD_UID;
+                       ui->uid = uid;
+                       ui->flags |= UI_FL_SLOT_USED;
+                       if (!uid_is_admissible(uid, urs))
+                               return 0;
+                       ui->flags |= UI_FL_ADMISSIBLE;
+                       ret = open_user_table(ui, flags & CREATE_USER_TABLE);
+                       if (ret < 0)
+                               return ret;
+
+                       if (ui_ptr)
+                               *ui_ptr = ui;
+                       return 1;
+               }
+               if (ui->uid != uid)
+                       continue;
+               if (ui_ptr)
+                       *ui_ptr = ui;
+               return 0;
+       }
+       return flags? -E_HASH_TABLE_OVERFLOW : -E_BAD_UID;
+}
+
+static char *get_uid_list_name(void)
+{
+       return make_message("%s/uid_list", conf.database_dir_arg);
+}
+
+void sort_hash_table(int (*comp)(const void *, const void *))
+{
+       qsort(uid_hash_table, uid_hash_table_size, sizeof(struct user_info),
+               comp);
+}
+
+int read_uid_file(struct uid_range *admissible_uids)
+{
+       size_t size;
+       uint32_t n;
+       char *filename = get_uid_list_name(), *map;
+       int ret = mmap_full_file(filename, O_RDONLY, (void **)&map, &size, NULL);
+       unsigned bits;
+
+       if (ret < 0) {
+               INFO_LOG("failed to map %s\n", filename);
+               free(filename);
+               return ret;
+       }
+       num_uids = size / 4;
+       INFO_LOG("found %u uids in %s\n", (unsigned)num_uids, filename);
+       free(filename);
+       /*
+        * Compute number of hash table bits. The hash table size must be a
+        * power of two and larger than the number of uids.
+        */
+       bits = 2;
+       while (1 << bits < num_uids)
+               bits++;
+       create_hash_table(bits);
+       for (n = 0; n < num_uids; n++) {
+               uint32_t uid = read_u32(map + n * sizeof(uid));
+               ret = search_uid(uid, admissible_uids, OPEN_USER_TABLE, NULL);
+               if (ret < 0)
+                       goto out;
+       }
+out:
+       adu_munmap(map, size);
+       return ret;
+}
+
+static int write_uid(struct user_info *ui, void *data)
+{
+       char **p = data;
+
+       write_u32(*p, ui->uid);
+       *p += sizeof(uint32_t);
+       return 1;
+}
+
+int write_uid_file(void)
+{
+       char *buf, *p, *filename;
+       size_t size = num_uids * sizeof(uint32_t);
+       int ret;
+
+       if (!num_uids)
+               return 0;
+       buf = p = adu_malloc(size);
+       ret = for_each_admissible_user(write_uid, &p);
+       if (ret < 0)
+               goto out;
+       filename = get_uid_list_name();
+       ret = adu_write_file(filename, buf, size);
+       free(filename);
+out:
+       free(buf);
+       return ret;
+}
diff --git a/user.h b/user.h
new file mode 100644 (file)
index 0000000..3eefab1
--- /dev/null
+++ b/user.h
@@ -0,0 +1,53 @@
+/** The columns of the id table. */
+enum user_table_columns {
+       /** The numer of the directory. */
+       UT_DIR_NUM,
+       /** The number of bytes of all regular files in this dir owned by this id. */
+       UT_BYTES,
+       /** The number of files in this dir owned by this id. */
+       UT_FILES,
+       /** Number of columns in this table. */
+       NUM_UT_COLUMNS
+};
+
+/** Information about one admissible user. */
+struct user_info {
+       /** User ID. */
+       uint32_t uid;
+       /** \sa enum uid_info_flags. */
+       uint32_t flags;
+       /** The user name.  */
+       char *pw_name;
+       /** The user table of this user.*/
+       struct osl_table *table;
+       /** Total number of files owned by this user. */
+       uint64_t files;
+       /** Total number of bytes owned by this user. */
+       uint64_t bytes;
+       /** Total number of directories that contain at least one file */
+       uint64_t dirs;
+       /** The description of the user table. */
+       struct osl_table_description *desc;
+};
+
+/** An opaque struct that contains info about which users are admissible. */
+struct uid_range;
+
+enum search_uid_flags {
+       OPEN_USER_TABLE = 1,
+       CREATE_USER_TABLE = 2,
+};
+int search_uid(uint32_t uid, struct uid_range *urs,
+               enum search_uid_flags flags, struct user_info **ui_ptr);
+
+int read_uid_file(struct uid_range *admissible_uids);
+int write_uid_file(void);
+
+void create_hash_table(unsigned bits);
+void sort_hash_table(int (*comp)(const void *, const void *));
+void free_hash_table(void);
+
+int for_each_admissible_user(int (*func)(struct user_info *, void *),
+               void *data);
+int parse_uid_arg(const char *orig_arg, struct uid_range **ur);
+void close_user_tables(void);