examples/hlt/hlt.c

   1 /*
   2  * Copyright (C) 2009 Andre Noll <maan@systemlinux.org>
   3  *
   4  * Licensed under the GPL v2. For licencing details see COPYING.
   5  */
   6
   7 /* A simple program that prints all hard links of a given directory. */
   8
   9 #include <inttypes.h>
  10 #include <osl.h>
  11 #include <string.h>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <sys/types.h>
  15 #include <sys/stat.h>
  16 #include <unistd.h>
  17 #include <sys/types.h>
  18 #include <dirent.h>
  19 #include <errno.h>
  20 #include <sys/mman.h>
  21 #include <fcntl.h>
  22
  23 /**
  24  * We are lazy here and use an osl table with only a single column of type
  25  * OSL_NO_STORAGE.  This is possible because we need only one red black tree
  26  * for hlt.  So we pack everything into one structure and use a fixed-size
  27  * column for the data of each (device, inode) pair.
  28  *
  29  * This approach keeps things simple but is a bit dangerous: As the compare
  30  * function for the red black tree, hld_compare, uses only the dev_id and the
  31  * inode fields of struct hard_link_data it's OK to modify the other fields of
  32  * the struct in-place.
  33  */
  34 enum hlt_columns {
  35         COL_HLD,
  36         NUM_HLT_COLUMNS
  37 };
  38
  39 /**
  40  * The data of one "row" of the table.
  41  */
  42 struct hard_link_data {
  43         /** The st_dev field from struct stat. */
  44         dev_t dev_id;
  45         /** The st_ino field from struct stat. */
  46         ino_t inode;
  47         /** The st_nlink field from struct stat. */
  48         nlink_t num_links;
  49         /** The array of pathnames. */
  50         char **paths;
  51         /** The size of \a paths. */
  52         unsigned array_size;
  53         /** The number of hard links found so far. */
  54         unsigned num_paths;
  55 };
  56
  57 /**
  58  * Compare two hard_link_data structs.
  59  *
  60  * \param obj1 Pointer to the first object.
  61  * \param obj2 Pointer to the second object.
  62  *
  63  * \return It returns an integer less than, equal to, or greater than zero if
  64  * \a obj1 is found, respectively, to be less than, to match, or be greater than
  65  * obj2.
  66  *
  67  * \sa strcmp(3), strncmp(3), osl_compare_func.
  68  */
  69 static int hld_compare(const struct osl_object *obj1, const struct osl_object *obj2)
  70 {
  71         const struct hard_link_data *hld1 = obj1->data;
  72         const struct hard_link_data *hld2 = obj2->data;
  73
  74         if (hld1->inode < hld2->inode)
  75                 return -1;
  76         if (hld1->inode > hld2->inode)
  77                 return 1;
  78         if (hld1->dev_id < hld2->dev_id)
  79                 return -1;
  80         if (hld1->dev_id > hld2->dev_id)
  81                 return 1;
  82         return 0;
  83 }
  84
  85 static struct osl_column_description hlt_table_cols[] = {
  86         [COL_HLD] = {
  87                 .storage_type = OSL_NO_STORAGE,
  88                 .storage_flags = OSL_RBTREE | OSL_UNIQUE | OSL_FIXED_SIZE,
  89                 .data_size = sizeof(struct hard_link_data),
  90                 .name = "hard link data",
  91                 .compare_function = hld_compare,
  92         },
  93 };
  94
  95 static struct osl_table *table;
  96
  97 static struct osl_table_description hlt_table_desc = {
  98         /* dir not needed because all cols have storage type NO_STORAGE */
  99         .dir = NULL,
 100         .name = "hlt",
 101         .num_columns = NUM_HLT_COLUMNS,
 102         .flags = 0,
 103         .column_descriptions = hlt_table_cols,
 104 };
 105
 106 static void print_usage_and_die(void)
 107 {
 108         fprintf(stderr, "usage:\n\thlt <dirname>\n");
 109         exit(EXIT_FAILURE);
 110 }
 111
 112 /* either succeeds or exits */
 113 static void create_table_or_die(int argc, char **argv)
 114 {
 115         struct stat statbuf;
 116         int ret;
 117
 118         /* some sanity checks */
 119         if (argc != 2)
 120                 print_usage_and_die();
 121         if (lstat(argv[1], &statbuf) == -1) {
 122                 fprintf(stderr, "no such dir: %s\n", argv[1]);
 123                 exit(EXIT_FAILURE);
 124         }
 125         if (!S_ISDIR(statbuf.st_mode)) {
 126                 fprintf(stderr, "not a dir: %s\n", argv[1]);
 127                 exit(EXIT_FAILURE);
 128         }
 129
 130         //fprintf(stderr, "col_desc: %p\n", hlt_table_desc.column_descriptions);
 131         /* create the osl table... */
 132         ret = osl_create_table(&hlt_table_desc);
 133         if (ret < 0) {
 134                 fprintf(stderr, "%s\n", osl_strerror(-ret));
 135                 exit(EXIT_FAILURE);
 136         }
 137         /* ...and open it. */
 138         ret = osl_open_table(&hlt_table_desc, &table);
 139         if (ret < 0) {
 140                 fprintf(stderr, "osl_open_table: %s\n", osl_strerror(-ret));
 141                 exit(EXIT_FAILURE);
 142         }
 143 }
 144
 145 static void *malloc_or_die(size_t size)
 146 {
 147         void *ret = malloc(size);
 148
 149         if (ret)
 150                 return ret;
 151         fprintf(stderr, "out of memory\n");
 152         exit(EXIT_FAILURE);
 153 }
 154
 155 static char *make_name(const char *dirname, const char *subdirname)
 156 {
 157         size_t len = strlen(dirname) + strlen(subdirname) + 2;
 158         char *name = malloc_or_die(len);
 159
 160         sprintf(name, "%s/%s", dirname, subdirname);
 161         return name;
 162 }
 163
 164 static int add_hard_link(char *path, struct stat *s)
 165 {
 166         int ret;
 167         struct osl_row *row;
 168         struct hard_link_data *entry;
 169
 170         /*
 171          * We need to find out whether a row containing the (dev_t, inode) pair
 172          * given by \a s already exists in the osl table. Therefore we init a
 173          * hard_link_data structure with only these two fields initialized...
 174          */
 175         struct hard_link_data hld = {
 176                 .dev_id = s->st_dev,
 177                 .inode = s->st_ino
 178         };
 179
 180         /* ... and make an osl object out of it. */
 181         struct osl_object obj = {
 182                 .data = &hld,
 183                 .size = sizeof(hld)
 184         };
 185
 186         /*
 187          * check whether there is a row with the same dev_id and inode values.
 188          */
 189         ret = osl_get_row(table, COL_HLD, &obj, &row);
 190
 191         /* Abort on real errors. */
 192         if (ret < 0 && ret != -E_OSL_RB_KEY_NOT_FOUND)
 193                 return ret;
 194
 195         if (ret < 0) { /* key not found, add a new row to the table. */
 196                 struct osl_object objs[NUM_HLT_COLUMNS];
 197
 198                 entry = malloc_or_die(sizeof(*entry));
 199                 memset(entry, 0, sizeof(*entry));
 200
 201                 /* copy relevant data from struct stat */
 202                 entry->dev_id = s->st_dev;
 203                 entry->inode = s->st_ino;
 204                 entry->num_links = s->st_nlink;
 205
 206                 entry->array_size = s->st_nlink; /* that's usually enough */
 207                 entry->paths = malloc_or_die(entry->array_size * sizeof(char *));
 208
 209                 /* Add the new row */
 210                 objs[COL_HLD].data = entry;
 211                 objs[COL_HLD].size = sizeof(*entry);
 212                 ret = osl_add_row(table, objs);
 213                 if (ret < 0) {
 214                         free(entry);
 215                         return ret;
 216                 }
 217         } else { /* OK, we have a row, retrieve the hld struct */
 218                 ret = osl_get_object(table, row, COL_HLD, &obj);
 219                 if (ret < 0)
 220                         return ret;
 221                 entry = obj.data;
 222         }
 223
 224         /*
 225          * Now 'entry' points to a struct hard_link_data and we may modify
 226          * everything in-place except dev_id and inode (these two fields must
 227          * not be changed directly because that would mess up the rbtree).
 228          *
 229          * So increase the counter and add the new path to the entry->paths
 230          * array.
 231          */
 232
 233         if (entry->num_paths >= entry->array_size) {
 234                 /*
 235                  * New hard links have been created by someone and the
 236                  * entry->paths array is too small. Double its size.
 237                  */
 238                 entry->array_size *= 2;
 239                 entry->paths = realloc(entry->paths,
 240                         entry->array_size * sizeof(char *));
 241                 if (!entry->paths) {
 242                         fprintf(stderr, "realloc error. array size: %u\n",
 243                                 entry->array_size);
 244                         exit(EXIT_FAILURE);
 245                 }
 246         }
 247
 248         entry->paths[entry->num_paths] = path;
 249         entry->num_paths++;
 250         return 1;
 251 }
 252
 253 /**
 254  * Traverse the given directory recursively. Each regular file
 255  * with hard link count > 1 is going to be added to the table.
 256  */
 257 static int populate_table(char *dirname)
 258 {
 259         struct dirent *entry;
 260         int ret;
 261         DIR *dir = opendir(dirname);
 262
 263         if (!dir) {
 264                 fprintf(stderr, "failed to open dir %s\n", dirname);
 265                 /* Ignore this error by returning success. */
 266                 return 1;
 267         }
 268         while ((entry = readdir(dir))) {
 269                 mode_t m;
 270                 struct stat s;
 271                 char *new_name;
 272
 273                 if (!strcmp(entry->d_name, "."))
 274                         continue;
 275                 if (!strcmp(entry->d_name, ".."))
 276                         continue;
 277                 new_name = make_name(dirname, entry->d_name);
 278                 if (lstat(new_name, &s) == -1) {
 279                         fprintf(stderr, "lstat error for %s (%s)\n",
 280                                 new_name, strerror(errno));
 281                         free(new_name);
 282                         continue;
 283                 }
 284                 m = s.st_mode;
 285                 if (S_ISDIR(m)) {
 286                         /* recurse and pass the name of the subdir */
 287                         ret = populate_table(new_name);
 288                         free(new_name);
 289                         if (ret < 0) /* fatal error */
 290                                 goto out;
 291                         continue;
 292                 }
 293                 if (!S_ISREG(m) || s.st_nlink < 2) {
 294                         free(new_name);
 295                         continue;
 296                 }
 297                 /* regular file with hard links, add it to the table */
 298                 add_hard_link(new_name, &s);
 299         }
 300         ret = 1; /* success */
 301 out:
 302         closedir(dir);
 303         return ret;
 304 }
 305
 306 static int print_row(struct osl_row *row, void *data)
 307 {
 308         struct hard_link_data *hld;
 309         struct osl_object obj;
 310         int i, ret = osl_get_object(table, row, COL_HLD, &obj);
 311
 312         if (ret < 0)
 313                 return ret;
 314         hld = obj.data;
 315         printf("%d/%d: Found %u/%u hard links:\n", (int)hld->dev_id,
 316                 (int)hld->inode, hld->num_paths, hld->num_links);
 317         for (i = 0; i < hld->num_paths; i++) {
 318                 printf("\t%s\n", hld->paths[i]);
 319                 free(hld->paths[i]);
 320         }
 321         free(hld->paths);
 322         return 1;
 323 }
 324
 325 int main(int argc, char **argv)
 326 {
 327         int ret;
 328
 329         create_table_or_die(argc, argv);
 330         ret = populate_table(argv[1]);
 331         if (ret < 0)
 332                 goto out;
 333         /*
 334          * Print results by iterating over all rows and calling print_row() for
 335          * each row.
 336          */
 337         ret = osl_rbtree_loop(table, COL_HLD, NULL, print_row);
 338 out:
 339         /* This frees the memory pointed to by the osl objects. */
 340         osl_close_table(table, OSL_FREE_VOLATILE);
 341         return ret < 0? EXIT_FAILURE : EXIT_SUCCESS;
 342 }