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