2 * Copyright (C) 2009 Andre Noll <maan@tuebingen.mpg.de>
4 * Licensed under the GPL v2. For licencing details see COPYING.
8 * A simple program that traverses a directory and prints groups of file names
9 * which are hard-linked to each other.
17 #include <sys/types.h>
20 #include <sys/types.h>
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.
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.
43 * The data of one "row" of the table.
45 struct hard_link_data {
46 /** The st_dev field from struct stat. */
48 /** The st_ino field from struct stat. */
50 /** The st_nlink field from struct stat. */
52 /** The array of pathnames. */
54 /** The size of \a paths. */
56 /** The number of hard links found so far. */
61 * Compare two hard_link_data structs.
63 * \param obj1 Pointer to the first object.
64 * \param obj2 Pointer to the second object.
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
70 * \sa strcmp(3), strncmp(3), osl_compare_func.
72 static int hld_compare(const struct osl_object *obj1, const struct osl_object *obj2)
74 const struct hard_link_data *hld1 = obj1->data;
75 const struct hard_link_data *hld2 = obj2->data;
77 if (hld1->inode < hld2->inode)
79 if (hld1->inode > hld2->inode)
81 if (hld1->dev_id < hld2->dev_id)
83 if (hld1->dev_id > hld2->dev_id)
88 static struct osl_column_description hlt_table_cols[] = {
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,
98 static struct osl_table *table;
100 static struct osl_table_description hlt_table_desc = {
101 /* dir not needed because all cols have storage type NO_STORAGE */
104 .num_columns = NUM_HLT_COLUMNS,
106 .column_descriptions = hlt_table_cols,
109 static void print_usage_and_die(void)
111 fprintf(stderr, "usage:\n\thlt <dirname>\n");
115 /* either succeeds or exits */
116 static void create_table_or_die(int argc, char **argv)
121 /* some sanity checks */
123 print_usage_and_die();
124 if (lstat(argv[1], &statbuf) == -1) {
125 fprintf(stderr, "no such dir: %s\n", argv[1]);
128 if (!S_ISDIR(statbuf.st_mode)) {
129 fprintf(stderr, "not a dir: %s\n", argv[1]);
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);
137 fprintf(stderr, "%s\n", osl_strerror(-ret));
140 /* ...and open it. */
141 ret = osl_open_table(&hlt_table_desc, &table);
143 fprintf(stderr, "osl_open_table: %s\n", osl_strerror(-ret));
148 static void *malloc_or_die(size_t size)
150 void *ret = malloc(size);
154 fprintf(stderr, "out of memory\n");
158 static char *make_name(const char *dirname, const char *subdirname)
160 size_t len = strlen(dirname) + strlen(subdirname) + 2;
161 char *name = malloc_or_die(len);
163 sprintf(name, "%s/%s", dirname, subdirname);
167 static int add_hard_link(char *path, struct stat *s)
171 struct hard_link_data *entry;
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...
178 struct hard_link_data hld = {
183 /* ... and make an osl object out of it. */
184 struct osl_object obj = {
190 * check whether there is a row with the same dev_id and inode values.
192 ret = osl_get_row(table, COL_HLD, &obj, &row);
194 /* Abort on real errors. */
195 if (ret < 0 && ret != -E_OSL_RB_KEY_NOT_FOUND)
198 if (ret < 0) { /* key not found, add a new row to the table. */
199 struct osl_object objs[NUM_HLT_COLUMNS];
201 entry = malloc_or_die(sizeof(*entry));
202 memset(entry, 0, sizeof(*entry));
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;
209 entry->array_size = s->st_nlink; /* that's usually enough */
210 entry->paths = malloc_or_die(entry->array_size * sizeof(char *));
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);
220 } else { /* OK, we have a row, retrieve the hld struct */
221 ret = osl_get_object(table, row, COL_HLD, &obj);
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).
232 * So increase the counter and add the new path to the entry->paths
236 if (entry->num_paths >= entry->array_size) {
238 * New hard links have been created by someone and the
239 * entry->paths array is too small. Double its size.
241 entry->array_size *= 2;
242 entry->paths = realloc(entry->paths,
243 entry->array_size * sizeof(char *));
245 fprintf(stderr, "realloc error. array size: %u\n",
251 entry->paths[entry->num_paths] = path;
257 * Traverse the given directory recursively. Each regular file
258 * with hard link count > 1 is going to be added to the table.
260 static int populate_table(char *dirname)
262 struct dirent *entry;
264 DIR *dir = opendir(dirname);
267 fprintf(stderr, "failed to open dir %s\n", dirname);
268 /* Ignore this error by returning success. */
271 while ((entry = readdir(dir))) {
276 if (!strcmp(entry->d_name, "."))
278 if (!strcmp(entry->d_name, ".."))
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));
289 /* recurse and pass the name of the subdir */
290 ret = populate_table(new_name);
292 if (ret < 0) /* fatal error */
296 if (!S_ISREG(m) || s.st_nlink < 2) {
300 /* regular file with hard links, add it to the table */
301 add_hard_link(new_name, &s);
303 ret = 1; /* success */
309 static int print_row(struct osl_row *row, void *data)
311 struct hard_link_data *hld;
312 struct osl_object obj;
313 int i, ret = osl_get_object(table, row, COL_HLD, &obj);
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]);
328 int main(int argc, char **argv)
332 create_table_or_die(argc, argv);
333 ret = populate_table(argv[1]);
337 * Print results by iterating over all rows and calling print_row() for
340 ret = osl_rbtree_loop(table, COL_HLD, NULL, print_row);
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;