adu.c

   1 /** \file adu.c The main functions used by all modes of operation. */
   2 #include "adu.h"
   3 #include <dirent.h> /* readdir() */
   4 #include <pwd.h>
   5 #include "format.h"
   6 #include "select.h"
   7
   8 #include "gcc-compat.h"
   9 #include "cmdline.h"
  10 #include "fd.h"
  11 #include "string.h"
  12 #include "error.h"
  13 #include "portable_io.h"
  14
  15 DEFINE_ERRLIST;
  16 int osl_errno;
  17
  18 /** In case a signal is received, its number is stored here. */
  19 static int signum;
  20
  21 /** Command line and config file options. */
  22 struct gengetopt_args_info conf;
  23
  24 /** Options passed to --select-options. */
  25 struct select_args_info select_conf;
  26
  27 /** The number of different uids found so far. */
  28 uint32_t num_uids = 0;
  29
  30 /** This is always a power of two. It is set in create_hash_table(). */
  31 static uint32_t uid_hash_table_size;
  32
  33 /**
  34  * Contains info for each user that owns at least one regular file.
  35  *
  36  * Even users that are not taken into account because of the --uid
  37  * option occupy a slot in this hash table. This allows to find out
  38  * quicky whether a uid is admissible. And yes, this has to be fast.
  39  */
  40 static struct user_info *uid_hash_table;
  41
  42 static inline int ui_used(struct user_info *ui)
  43 {
  44         return ui->flags & UI_FL_SLOT_USED;
  45 }
  46
  47 static inline int ui_admissible(struct user_info *ui)
  48 {
  49         return ui->flags & UI_FL_ADMISSIBLE;
  50 }
  51
  52 /**
  53  * The table containing the directory names and statistics.
  54  */
  55 struct osl_table *dir_table = NULL;
  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 /*
 146  * The columns of the per-user tables.
 147  *
 148  * Adu tracks disk usage on a per-user basis. For each user, a user table is
 149  * being created. The rows of the user table have three columns: The directory
 150  * number that may be resolved to the path using the directory table, the
 151  * number of bytes and the number of files in that directory owned by the given
 152  * user.
 153  */
 154 static struct osl_column_description user_table_cols[] = {
 155         [UT_DIR_NUM] = {
 156                 .storage_type = OSL_MAPPED_STORAGE,
 157                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
 158                 .name = "dir_num",
 159                 .compare_function = uint64_compare,
 160                 .data_size = sizeof(uint64_t)
 161         },
 162         [UT_BYTES] = {
 163                 .storage_type = OSL_MAPPED_STORAGE,
 164                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
 165                 .compare_function = size_compare,
 166                 .name = "num_bytes",
 167                 .data_size = sizeof(uint64_t)
 168         },
 169         [UT_FILES] = {
 170                 .storage_type = OSL_MAPPED_STORAGE,
 171                 .storage_flags = OSL_RBTREE | OSL_FIXED_SIZE,
 172                 .compare_function = size_compare,
 173                 .name = "num_files",
 174                 .data_size = sizeof(uint64_t)
 175         },
 176 };
 177
 178 /**
 179  * The log function.
 180  *
 181  * \param ll Loglevel.
 182  * \param fmt Usual format string.
 183  *
 184  * All XXX_LOG() macros use this function.
 185  */
 186 __printf_2_3 void __log(int ll, const char* fmt,...)
 187 {
 188         va_list argp;
 189         FILE *outfd;
 190         struct tm *tm;
 191         time_t t1;
 192         char str[255] = "";
 193
 194         if (ll < conf.loglevel_arg)
 195                 return;
 196         outfd = stderr;
 197         time(&t1);
 198         tm = localtime(&t1);
 199         strftime(str, sizeof(str), "%b %d %H:%M:%S", tm);
 200         fprintf(outfd, "%s ", str);
 201         va_start(argp, fmt);
 202         vfprintf(outfd, fmt, argp);
 203         va_end(argp);
 204 }
 205
 206 static int open_user_table(struct user_info *ui, int create)
 207 {
 208         int ret;
 209         struct passwd *pw;
 210
 211         ui->desc = adu_malloc(sizeof(*ui->desc));
 212         ui->desc->num_columns = NUM_UT_COLUMNS;
 213         ui->desc->flags = 0;
 214         ui->desc->column_descriptions = user_table_cols;
 215         ui->desc->dir = adu_strdup(conf.database_dir_arg);
 216         ui->desc->name = make_message("%u", (unsigned)ui->uid);
 217         pw = getpwuid(ui->uid);
 218         if (pw && pw->pw_name)
 219                 ui->pw_name = adu_strdup(pw->pw_name);
 220
 221         INFO_LOG(".............................uid #%u: %u\n",
 222                 (unsigned)num_uids, (unsigned)ui->uid);
 223         if (create) {
 224                 ret = osl(osl_create_table(ui->desc));
 225                 if (ret < 0)
 226                         goto err;
 227                 num_uids++;
 228         }
 229         ret = osl(osl_open_table(ui->desc, &ui->table));
 230         if (ret < 0)
 231                 goto err;
 232         return 1;
 233 err:
 234         free((char *)ui->desc->name);
 235         free((char *)ui->desc->dir);
 236         free(ui->pw_name);
 237         free(ui->desc);
 238         ui->desc->name = NULL;
 239         ui->desc->dir = NULL;
 240         ui->desc = NULL;
 241         ui->table = NULL;
 242         ui->flags = 0;
 243         return ret;
 244 }
 245
 246 int for_each_admissible_user(int (*func)(struct user_info *, void *),
 247                 void *data)
 248 {
 249         struct user_info *ui = uid_hash_table;
 250
 251         if (!ui)
 252                 return -ERRNO_TO_ERROR(EFAULT);
 253
 254         for (; ui < uid_hash_table + uid_hash_table_size; ui++) {
 255                 int ret;
 256
 257                 if (!ui_used(ui) || !ui_admissible(ui))
 258                         continue;
 259                 ret = func(ui, data);
 260                 if (ret < 0)
 261                         return ret;
 262         }
 263         return 1;
 264 }
 265
 266 #define PRIME1 0xb11924e1
 267 #define PRIME2 0x01000193
 268
 269 void create_hash_table(unsigned bits)
 270 {
 271         uid_hash_table_size = 1 << bits;
 272         uid_hash_table = adu_calloc(uid_hash_table_size *
 273                 sizeof(struct user_info));
 274 }
 275
 276 static void free_hash_table(void)
 277 {
 278         free(uid_hash_table);
 279         uid_hash_table = NULL;
 280 }
 281
 282 static void close_dir_table(void)
 283 {
 284         int ret;
 285
 286         if (!dir_table)
 287                 return;
 288         ret = osl(osl_close_table(dir_table, OSL_MARK_CLEAN));
 289         if (ret < 0)
 290                 ERROR_LOG("failed to close dir table: %s\n", adu_strerror(-ret));
 291         free((char *)dir_table_desc.dir);
 292         dir_table = NULL;
 293 }
 294
 295 static int close_user_table(struct user_info *ui, __a_unused void *data)
 296 {
 297         int ret;
 298
 299         ret = osl(osl_close_table(ui->table, OSL_MARK_CLEAN));
 300         if (ret < 0)
 301                 ERROR_LOG("failed to close user table %u: %s\n",
 302                         (unsigned) ui->uid, adu_strerror(-ret));
 303         free((char *)ui->desc->name);
 304         ui->desc->name = NULL;
 305         free((char *)ui->desc->dir);
 306         ui->desc->dir = NULL;
 307         free(ui->pw_name);
 308         ui->pw_name = NULL;
 309         free(ui->desc);
 310         ui->desc = NULL;
 311         ui->table = NULL;
 312         ui->flags = 0;
 313         return 1;
 314 }
 315
 316 static void close_user_tables(void)
 317 {
 318         for_each_admissible_user(close_user_table, NULL);
 319 }
 320
 321 void close_all_tables(void)
 322 {
 323         close_dir_table();
 324         close_user_tables();
 325         free_hash_table();
 326 }
 327
 328 static void signal_handler(int s)
 329 {
 330         signum = s;
 331 }
 332
 333 void check_signals(void)
 334 {
 335         if (likely(!signum))
 336                 return;
 337         EMERG_LOG("caught signal %d\n", signum);
 338         close_all_tables();
 339         exit(EXIT_FAILURE);
 340 }
 341
 342 static int init_signals(void)
 343 {
 344         if (signal(SIGINT, &signal_handler) == SIG_ERR)
 345                 return -E_SIGNAL_SIG_ERR;
 346         if (signal(SIGTERM, &signal_handler) == SIG_ERR)
 347                 return -E_SIGNAL_SIG_ERR;
 348         if (signal(SIGPIPE, &signal_handler) == SIG_ERR)
 349                 return -E_SIGNAL_SIG_ERR;
 350         return 1;
 351 }
 352
 353 /*
 354  * We use a hash table of size s=2^uid_hash_bits to map the uids into the
 355  * interval [0..s]. Hash collisions are treated by open addressing, i.e.
 356  * unused slots in the table are used to store different uids that hash to the
 357  * same slot.
 358  *
 359  * If a hash collision occurs, different slots are successively probed in order
 360  * to find an unused slot for the new uid. Probing is implemented via a second
 361  * hash function that maps the uid to h=(uid * PRIME2) | 1, which is always an
 362  * odd number.
 363  *
 364  * An odd number is sufficient to make sure each entry of the hash table gets
 365  * probed for probe_num between 0 and s-1 because s is a power of two, hence
 366  * the second hash value has never a common divisor with the hash table size.
 367  * IOW: h is invertible in the ring [0..s].
 368  */
 369 static uint32_t double_hash(uint32_t uid, uint32_t probe_num)
 370 {
 371         return (uid * PRIME1 + ((uid * PRIME2) | 1) * probe_num)
 372                 % uid_hash_table_size;
 373 }
 374
 375 static int uid_is_admissible(uint32_t uid, struct uid_range *urs)
 376 {
 377         struct uid_range *ur;
 378         int ret = 1;
 379
 380         if (!urs) /* empty array means all uids are allowed */
 381                 return 1;
 382         FOR_EACH_UID_RANGE(ur, urs)
 383                 if (ur->low <= uid && ur->high >= uid)
 384                         goto out;
 385         ret = 0;
 386 out:
 387         DEBUG_LOG("uid %u is %sadmissible\n", (unsigned)uid,
 388                 ret? "" : "not ");
 389         return ret;
 390 }
 391
 392 int search_uid(uint32_t uid, struct uid_range *urs,
 393                 enum search_uid_flags flags, struct user_info **ui_ptr)
 394 {
 395         uint32_t p;
 396
 397         for (p = 0; p < uid_hash_table_size; p++) {
 398                 struct user_info *ui = uid_hash_table + double_hash(uid, p);
 399
 400                 if (!ui_used(ui)) {
 401                         int ret;
 402                         if (!flags)
 403                                 return -E_BAD_UID;
 404                         ui->uid = uid;
 405                         ui->flags |= UI_FL_SLOT_USED;
 406                         if (!uid_is_admissible(uid, urs))
 407                                 return 0;
 408                         ui->flags |= UI_FL_ADMISSIBLE;
 409                         ret = open_user_table(ui, flags & CREATE_USER_TABLE);
 410                         if (ret < 0)
 411                                 return ret;
 412
 413                         if (ui_ptr)
 414                                 *ui_ptr = ui;
 415                         return 1;
 416                 }
 417                 if (ui->uid != uid)
 418                         continue;
 419                 if (ui_ptr)
 420                         *ui_ptr = ui;
 421                 return 0;
 422         }
 423         return flags? -E_HASH_TABLE_OVERFLOW : -E_BAD_UID;
 424 }
 425
 426 char *get_uid_list_name(void)
 427 {
 428         return make_message("%s/uid_list", conf.database_dir_arg);
 429 }
 430
 431 void sort_hash_table(int (*comp)(const void *, const void *))
 432 {
 433         qsort(uid_hash_table, uid_hash_table_size, sizeof(struct user_info),
 434                 comp);
 435 }
 436
 437 int open_dir_table(int create)
 438 {
 439         dir_table_desc.dir = adu_strdup(conf.database_dir_arg);
 440
 441         if (create) {
 442                 int ret = osl(osl_create_table(&dir_table_desc));
 443                 if (ret < 0) {
 444                         free((char *)dir_table_desc.dir);
 445                         return ret;
 446                 }
 447         }
 448         return osl(osl_open_table(&dir_table_desc, &dir_table));
 449 }
 450
 451 static int check_args(void)
 452 {
 453         if (conf.create_given && !conf.base_dir_given)
 454                 return -E_SYNTAX;
 455
 456         /* remove trailing slashes from base-dir arg */
 457         if (conf.base_dir_given) {
 458                 size_t len = strlen(conf.base_dir_arg);
 459                 for (;;) {
 460                         if (!len) /* empty string */
 461                                 return -ERRNO_TO_ERROR(EINVAL);
 462                         if (!--len) /* length 1 is always OK */
 463                                 break;
 464                         if (conf.base_dir_arg[len] != '/')
 465                                 break; /* no trailing slash, also OK */
 466                         conf.base_dir_arg[len] = '\0';
 467                 }
 468         }
 469         return 1;
 470 }
 471
 472 static int print_complete_help_and_die(void)
 473 {
 474         const char **line;
 475         select_cmdline_parser_init(&select_conf);
 476
 477         printf("%s-%s\n", CMDLINE_PARSER_PACKAGE, CMDLINE_PARSER_VERSION);
 478         printf("%s\n\n", gengetopt_args_info_purpose);
 479         printf("%s\n\n", gengetopt_args_info_usage);
 480
 481         if (conf.help_given)
 482                 line = gengetopt_args_info_help;
 483         else
 484                 line = gengetopt_args_info_detailed_help;
 485         for (; *line; line++)
 486                 printf("%s\n", *line);
 487
 488         if (conf.help_given)
 489                 line = select_args_info_help;
 490         else
 491                 line  = select_args_info_detailed_help;
 492         printf("Select options:\n");
 493         for (; *line; line++)
 494                 printf("%s\n", *line);
 495
 496         printf("Interactive commands:\n");
 497         print_interactive_help();
 498         exit(EXIT_FAILURE);
 499 }
 500
 501 int main(int argc, char **argv)
 502 {
 503         int ret;
 504         struct cmdline_parser_params params = {
 505                 .override = 0,
 506                 .initialize = 1,
 507                 .check_required = 0,
 508                 .check_ambiguity = 0,
 509                 .print_errors = 0
 510         };
 511         /* ignore errors and print complete help if --help was given */
 512         cmdline_parser_ext(argc, argv, &conf, &params);
 513         if (conf.help_given || conf.detailed_help_given)
 514                 print_complete_help_and_die();
 515         params.check_required = 1;
 516         params.check_ambiguity = 1;
 517         params.print_errors = 1;
 518         ret = cmdline_parser_ext(argc, argv, &conf, &params);
 519         if (ret)
 520                 exit(EXIT_FAILURE);
 521
 522         ret = check_args();
 523         if (ret < 0)
 524                 goto out;
 525         ret = init_signals();
 526         if (ret < 0)
 527                 goto out;
 528         ret = -E_SYNTAX;
 529         if (conf.select_given)
 530                 ret = com_select();
 531         else if (conf.create_given)
 532                 ret = com_create();
 533         else
 534                 ret = com_interactive();
 535         if (ret < 0)
 536                 goto out;
 537 out:
 538         if (ret < 0) {
 539                 ERROR_LOG("%s\n", adu_strerror(-ret));
 540                 return -EXIT_FAILURE;
 541         }
 542         return EXIT_SUCCESS;
 543 }