adu.c

   1 #include "adu.h"
   2 #include <dirent.h> /* readdir() */
   3 #include <pwd.h>
   4
   5 #include "gcc-compat.h"
   6 #include "cmdline.h"
   7 #include "fd.h"
   8 #include "string.h"
   9 #include "error.h"
  10 #include "portable_io.h"
  11
  12 DEFINE_ERRLIST;
  13 int osl_errno;
  14
  15 /** In case a signal is received, its number is stored here. */
  16 static int signum;
  17
  18 /** Command line and config file options. */
  19 struct gengetopt_args_info conf;
  20
  21 /** The number of different uids found so far. */
  22 uint32_t num_uids = 0;
  23
  24 /** This is always a power of two. It is set in create_hash_table(). */
  25 static uint32_t uid_hash_table_size;
  26
  27 /**
  28  * Contains info for each user that owns at least one regular file.
  29  *
  30  * Even users that are not taken into account because of the --uid
  31  * option occupy a slot in this hash table. This allows to find out
  32  * quicky whether a uid is admissible. And yes, this has to be fast.
  33  */
  34 static struct user_info *uid_hash_table;
  35
  36 static inline int ui_used(struct user_info *ui)
  37 {
  38         return ui->flags & UI_FL_SLOT_USED;
  39 }
  40
  41 static inline int ui_admissible(struct user_info *ui)
  42 {
  43         return ui->flags & UI_FL_ADMISSIBLE;
  44 }
  45
  46 /**
  47  * The table containing the directory names and statistics.
  48  */
  49 struct osl_table *dir_table = NULL;
  50
  51 /**
  52  * The array of all uid ranges that were given at the command line.
  53  */
  54 struct uid_range *admissible_uids;
  55
  56
  57 /**
  58  * Compare the size of two directories
  59  *
  60  * \param obj1 Pointer to the first object.
  61  * \param obj2 Pointer to the second object.
  62  *
  63  * This function first compares the size values as usual integers. If they compare as
  64  * equal, the address of \a obj1 and \a obj2 are compared. So this compare function
  65  * returns zero if and only if \a obj1 and \a obj2 point to the same memory area.
  66  */
  67 static int size_compare(const struct osl_object *obj1, const struct osl_object *obj2)
  68 {
  69         uint64_t d1 = *(uint64_t *)obj1->data;
  70         uint64_t d2 = *(uint64_t *)obj2->data;
  71         int ret = NUM_COMPARE(d2, d1);
  72
  73         if (ret)
  74                 return ret;
  75         //INFO_LOG("addresses: %p, %p\n", obj1->data, obj2->data);
  76         return NUM_COMPARE(obj2->data, obj1->data);
  77 }
  78
  79 /**
  80  * Compare two osl objects pointing to unsigned integers of 64 bit size.
  81  *
  82  * \param obj1 Pointer to the first integer.
  83  * \param obj2 Pointer to the second integer.
  84  *
  85  * \return The values required for an osl compare function.
  86  *
  87  * \sa osl_compare_func, osl_hash_compare().
  88  */
  89 static int uint64_compare(const struct osl_object *obj1,
  90                 const struct osl_object *obj2)
  91 {
  92         uint64_t d1 = read_u64((const char *)obj1->data);
  93         uint64_t d2 = read_u64((const char *)obj2->data);
  94
  95         if (d1 < d2)
  96                 return 1;
  97         if (d1 > d2)
  98                 return -1;
  99         return 0;
 100 }
 101
 102 static struct osl_column_description dir_table_cols[] = {
 103         [DT_NAME] = {
 104                 .storage_type = OSL_MAPPED_STORAGE,
 105                 .storage_flags = 0,
 106                 .name = "dir",
 107         },
 108         [DT_NUM] = {
 109                 .storage_type = OSL_MAPPED_STORAGE,
 110                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
 111                 .name = "num",
 112                 .compare_function = uint64_compare,
 113                 .data_size = sizeof(uint64_t)
 114         },
 115         [DT_PARENT_NUM] = {
 116                 .storage_type = OSL_MAPPED_STORAGE,
 117                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
 118                 .name = "parent_num",
 119                 .compare_function = size_compare,
 120                 .data_size = sizeof(uint64_t)
 121         },
 122         [DT_BYTES] = {
 123                 .storage_type = OSL_MAPPED_STORAGE,
 124                 .storage_flags =  OSL_RBTREE | OSL_FIXED_SIZE,
 125                 .compare_function = size_compare,
 126                 .name = "num_bytes",
 127                 .data_size = sizeof(uint64_t)
 128         },
 129         [DT_FILES] = {
 130                 .storage_type = OSL_MAPPED_STORAGE,
 131                 .storage_flags =  OSL_RBTREE | OSL_FIXED_SIZE,
 132                 .compare_function = size_compare,
 133                 .name = "num_files",
 134                 .data_size = sizeof(uint64_t)
 135         }
 136 };
 137
 138 static struct osl_table_description dir_table_desc = {
 139         .name = "dir_table",
 140         .num_columns = NUM_DT_COLUMNS,
 141         .flags = 0,
 142         .column_descriptions = dir_table_cols,
 143 };
 144
 145 static struct osl_column_description user_table_cols[] = {
 146         [UT_DIR_NUM] = {
 147                 .storage_type = OSL_MAPPED_STORAGE,
 148                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
 149                 .name = "dir_num",
 150                 .compare_function = uint64_compare,
 151                 .data_size = sizeof(uint64_t)
 152         },
 153         [UT_BYTES] = {
 154                 .storage_type = OSL_MAPPED_STORAGE,
 155                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
 156                 .compare_function = size_compare,
 157                 .name = "num_bytes",
 158                 .data_size = sizeof(uint64_t)
 159         },
 160         [UT_FILES] = {
 161                 .storage_type = OSL_MAPPED_STORAGE,
 162                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
 163                 .compare_function = size_compare,
 164                 .name = "num_files",
 165                 .data_size = sizeof(uint64_t)
 166         },
 167 };
 168
 169 /**
 170  * The log function.
 171  *
 172  * \param ll Loglevel.
 173  * \param fml Usual format string.
 174  *
 175  * All XXX_LOG() macros use this function.
 176  */
 177 __printf_2_3 void __log(int ll, const char* fmt,...)
 178 {
 179         va_list argp;
 180         FILE *outfd;
 181         struct tm *tm;
 182         time_t t1;
 183         char str[255] = "";
 184
 185         if (ll < conf.loglevel_arg)
 186                 return;
 187         outfd = stderr;
 188         time(&t1);
 189         tm = localtime(&t1);
 190         strftime(str, sizeof(str), "%b %d %H:%M:%S", tm);
 191         fprintf(outfd, "%s ", str);
 192         va_start(argp, fmt);
 193         vfprintf(outfd, fmt, argp);
 194         va_end(argp);
 195 }
 196
 197 static int open_user_table(struct user_info *ui, int create)
 198 {
 199         int ret;
 200         struct passwd *pw;
 201
 202         ui->desc = adu_malloc(sizeof(*ui->desc));
 203         ui->desc->num_columns = NUM_UT_COLUMNS;
 204         ui->desc->flags = 0;
 205         ui->desc->column_descriptions = user_table_cols;
 206         ui->desc->dir = adu_strdup(conf.database_dir_arg);
 207         ui->desc->name = make_message("%u", (unsigned)ui->uid);
 208         pw = getpwuid(ui->uid);
 209         if (pw && pw->pw_name)
 210                 ui->pw_name = adu_strdup(pw->pw_name);
 211
 212         INFO_LOG(".............................uid #%u: %u\n",
 213                 (unsigned)num_uids, (unsigned)ui->uid);
 214         if (create) {
 215                 ret = osl(osl_create_table(ui->desc));
 216                 if (ret < 0)
 217                         goto err;
 218                 num_uids++;
 219         }
 220         ret = osl(osl_open_table(ui->desc, &ui->table));
 221         if (ret < 0)
 222                 goto err;
 223         return 1;
 224 err:
 225         free((char *)ui->desc->name);
 226         free((char *)ui->desc->dir);
 227         free(ui->pw_name);
 228         free(ui->desc);
 229         ui->desc->name = NULL;
 230         ui->desc->dir = NULL;
 231         ui->desc = NULL;
 232         ui->table = NULL;
 233         ui->flags = 0;
 234         return ret;
 235 }
 236
 237 int for_each_admissible_user(int (*func)(struct user_info *, void *),
 238                 void *data)
 239 {
 240         struct user_info *ui = uid_hash_table;
 241
 242         if (!ui)
 243                 return -ERRNO_TO_ERROR(EFAULT);
 244
 245         for (; ui < uid_hash_table + uid_hash_table_size; ui++) {
 246                 int ret;
 247
 248                 if (!ui_used(ui) || !ui_admissible(ui))
 249                         continue;
 250                 ret = func(ui, data);
 251                 if (ret < 0)
 252                         return ret;
 253         }
 254         return 1;
 255 }
 256
 257 #define PRIME1 0xb11924e1
 258 #define PRIME2 0x01000193
 259
 260 void create_hash_table(unsigned bits)
 261 {
 262         uid_hash_table_size = 1 << bits;
 263         uid_hash_table = adu_calloc(uid_hash_table_size *
 264                 sizeof(struct user_info));
 265 }
 266
 267 static void free_hash_table(void)
 268 {
 269         free(uid_hash_table);
 270         uid_hash_table = NULL;
 271 }
 272
 273 static void close_dir_table(void)
 274 {
 275         int ret;
 276
 277         if (!dir_table)
 278                 return;
 279         ret = osl(osl_close_table(dir_table, OSL_MARK_CLEAN));
 280         if (ret < 0)
 281                 ERROR_LOG("failed to close dir table: %s\n", adu_strerror(-ret));
 282         free((char *)dir_table_desc.dir);
 283         dir_table = NULL;
 284 }
 285
 286 static int close_user_table(struct user_info *ui, __a_unused void *data)
 287 {
 288         int ret;
 289
 290         ret = osl(osl_close_table(ui->table, OSL_MARK_CLEAN));
 291         if (ret < 0)
 292                 ERROR_LOG("failed to close user table %u: %s\n",
 293                         (unsigned) ui->uid, adu_strerror(-ret));
 294         free((char *)ui->desc->name);
 295         ui->desc->name = NULL;
 296         free((char *)ui->desc->dir);
 297         ui->desc->dir = NULL;
 298         free(ui->pw_name);
 299         ui->pw_name = NULL;
 300         free(ui->desc);
 301         ui->desc = NULL;
 302         ui->table = NULL;
 303         ui->flags = 0;
 304         return 1;
 305 }
 306
 307 static void close_user_tables(void)
 308 {
 309         for_each_admissible_user(close_user_table, NULL);
 310 }
 311
 312 void close_all_tables(void)
 313 {
 314         close_dir_table();
 315         close_user_tables();
 316         free_hash_table();
 317 }
 318
 319 static void signal_handler(int s)
 320 {
 321         signum = s;
 322 }
 323
 324 void check_signals(void)
 325 {
 326         if (likely(!signum))
 327                 return;
 328         EMERG_LOG("caught signal %d\n", signum);
 329         close_all_tables();
 330         exit(EXIT_FAILURE);
 331 }
 332
 333 static int init_signals(void)
 334 {
 335         if (signal(SIGINT, &signal_handler) == SIG_ERR)
 336                 return -E_SIGNAL_SIG_ERR;
 337         if (signal(SIGTERM, &signal_handler) == SIG_ERR)
 338                 return -E_SIGNAL_SIG_ERR;
 339         if (signal(SIGPIPE, &signal_handler) == SIG_ERR)
 340                 return -E_SIGNAL_SIG_ERR;
 341         return 1;
 342 }
 343
 344 /*
 345  * We use a hash table of size s=2^uid_hash_bits to map the uids into the
 346  * interval [0..s]. Hash collisions are treated by open addressing, i.e.
 347  * unused slots in the table are used to store different uids that hash to the
 348  * same slot.
 349  *
 350  * If a hash collision occurs, different slots are successively probed in order
 351  * to find an unused slot for the new uid. Probing is implemented via a second
 352  * hash function that maps the uid to h=(uid * PRIME2) | 1, which is always an
 353  * odd number.
 354  *
 355  * An odd number is sufficient to make sure each entry of the hash table gets
 356  * probed for probe_num between 0 and s-1 because s is a power of two, hence
 357  * the second hash value has never a common divisor with the hash table size.
 358  * IOW: h is invertible in the ring [0..s].
 359  */
 360 static uint32_t double_hash(uint32_t uid, uint32_t probe_num)
 361 {
 362         return (uid * PRIME1 + ((uid * PRIME2) | 1) * probe_num)
 363                 % uid_hash_table_size;
 364 }
 365
 366 static int uid_is_admissible(uint32_t uid)
 367 {
 368         int i;
 369
 370         for (i = 0; i < conf.uid_given; i++) {
 371                 struct uid_range *ur = admissible_uids + i;
 372
 373                 if (ur->low <= uid && ur->high >= uid)
 374                         break;
 375         }
 376         i = !conf.uid_given || i < conf.uid_given;
 377         DEBUG_LOG("uid %u is %sadmissible\n", (unsigned)uid,
 378                 i? "" : "not ");
 379         return i;
 380 }
 381
 382 int search_uid(uint32_t uid, enum search_uid_flags flags,
 383                 struct user_info **ui_ptr)
 384 {
 385         uint32_t p;
 386
 387         for (p = 0; p < uid_hash_table_size; p++) {
 388                 struct user_info *ui = uid_hash_table + double_hash(uid, p);
 389
 390                 if (!ui_used(ui)) {
 391                         int ret;
 392                         if (!flags)
 393                                 return -E_BAD_UID;
 394                         ui->uid = uid;
 395                         ui->flags |= UI_FL_SLOT_USED;
 396                         if (!uid_is_admissible(uid))
 397                                 return 0;
 398                         ui->flags |= UI_FL_ADMISSIBLE;
 399                         ret = open_user_table(ui, flags & CREATE_USER_TABLE);
 400                         if (ret < 0)
 401                                 return ret;
 402
 403                         if (ui_ptr)
 404                                 *ui_ptr = ui;
 405                         return 1;
 406                 }
 407                 if (ui->uid != uid)
 408                         continue;
 409                 if (ui_ptr)
 410                         *ui_ptr = ui;
 411                 return 0;
 412         }
 413         return flags? -E_HASH_TABLE_OVERFLOW : -E_BAD_UID;
 414 }
 415
 416 char *get_uid_list_name(void)
 417 {
 418         return make_message("%s/uid_list", conf.database_dir_arg);
 419 }
 420
 421 void sort_hash_table(int (*comp)(const void *, const void *))
 422 {
 423         qsort(uid_hash_table, uid_hash_table_size, sizeof(struct user_info),
 424                 comp);
 425 }
 426
 427 int open_dir_table(int create)
 428 {
 429         dir_table_desc.dir = adu_strdup(conf.database_dir_arg);
 430
 431         if (create) {
 432                 int ret = osl(osl_create_table(&dir_table_desc));
 433                 if (ret < 0) {
 434                         free((char *)dir_table_desc.dir);
 435                         return ret;
 436                 }
 437         }
 438         return osl(osl_open_table(&dir_table_desc, &dir_table));
 439 }
 440
 441 static int check_args(void)
 442 {
 443         int i, ret;
 444
 445
 446         if (conf.create_given && !conf.base_dir_given)
 447                 return -E_SYNTAX;
 448
 449         /* remove trailing slashes from base-dir arg */
 450         if (conf.base_dir_given) {
 451                 size_t len = strlen(conf.base_dir_arg);
 452                 for (;;) {
 453                         if (!len) /* empty string */
 454                                 return -ERRNO_TO_ERROR(EINVAL);
 455                         if (!--len) /* length 1 is always OK */
 456                                 break;
 457                         if (conf.base_dir_arg[len] != '/')
 458                                 break; /* no trailing slash, also OK */
 459                         conf.base_dir_arg[len] = '\0';
 460                 }
 461         }
 462         if (!conf.uid_given)
 463                 return 0;
 464         admissible_uids = adu_malloc(conf.uid_given * sizeof(*admissible_uids));
 465         for (i = 0; i < conf.uid_given; i++) {
 466                 ret = parse_uid_range(conf.uid_arg[i], admissible_uids + i);
 467                 if (ret < 0)
 468                         goto err;
 469         }
 470         return 1;
 471 err:
 472         free(admissible_uids);
 473         admissible_uids = NULL;
 474         return ret;
 475 }
 476
 477 int main(int argc, char **argv)
 478 {
 479         int ret;
 480         struct cmdline_parser_params params = {
 481                 .override = 0,
 482                 .initialize = 1,
 483                 .check_required = 1,
 484                 .check_ambiguity = 1,
 485                 .print_errors = 1
 486         };
 487
 488         cmdline_parser_ext(argc, argv, &conf, &params); /* aborts on errors */
 489         ret = check_args();
 490         if (ret < 0)
 491                 goto out;
 492         ret = init_signals();
 493         if (ret < 0)
 494                 goto out;
 495         ret = -E_SYNTAX;
 496         if (conf.select_given)
 497                 ret = com_select();
 498         else if (conf.create_given)
 499                 ret = com_create();
 500         else
 501                 ret = com_interactive();
 502         if (ret < 0)
 503                 goto out;
 504 out:
 505         free(admissible_uids);
 506         if (ret < 0) {
 507                 ERROR_LOG("%s\n", adu_strerror(-ret));
 508                 return -EXIT_FAILURE;
 509         }
 510         return EXIT_SUCCESS;
 511 }