examples/hlt/hlt.c

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