2 * Copyright (C) 2009 Andre Noll <maan@tuebingen.mpg.de>
4 * Licensed under the GPL v2. For licencing details see COPYING.
7 /* A simple program that prints all hard links of a given directory. */
14 #include <sys/types.h>
17 #include <sys/types.h>
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.
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.
40 * The data of one "row" of the table.
42 struct hard_link_data {
43 /** The st_dev field from struct stat. */
45 /** The st_ino field from struct stat. */
47 /** The st_nlink field from struct stat. */
49 /** The array of pathnames. */
51 /** The size of \a paths. */
53 /** The number of hard links found so far. */
58 * Compare two hard_link_data structs.
60 * \param obj1 Pointer to the first object.
61 * \param obj2 Pointer to the second object.
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
67 * \sa strcmp(3), strncmp(3), osl_compare_func.
69 static int hld_compare(const struct osl_object *obj1, const struct osl_object *obj2)
71 const struct hard_link_data *hld1 = obj1->data;
72 const struct hard_link_data *hld2 = obj2->data;
74 if (hld1->inode < hld2->inode)
76 if (hld1->inode > hld2->inode)
78 if (hld1->dev_id < hld2->dev_id)
80 if (hld1->dev_id > hld2->dev_id)
85 static struct osl_column_description hlt_table_cols[] = {
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,
95 static struct osl_table *table;
97 static struct osl_table_description hlt_table_desc = {
98 /* dir not needed because all cols have storage type NO_STORAGE */
101 .num_columns = NUM_HLT_COLUMNS,
103 .column_descriptions = hlt_table_cols,
106 static void print_usage_and_die(void)
108 fprintf(stderr, "usage:\n\thlt <dirname>\n");
112 /* either succeeds or exits */
113 static void create_table_or_die(int argc, char **argv)
118 /* some sanity checks */
120 print_usage_and_die();
121 if (lstat(argv[1], &statbuf) == -1) {
122 fprintf(stderr, "no such dir: %s\n", argv[1]);
125 if (!S_ISDIR(statbuf.st_mode)) {
126 fprintf(stderr, "not a dir: %s\n", argv[1]);
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);
134 fprintf(stderr, "%s\n", osl_strerror(-ret));
137 /* ...and open it. */
138 ret = osl_open_table(&hlt_table_desc, &table);
140 fprintf(stderr, "osl_open_table: %s\n", osl_strerror(-ret));
145 static void *malloc_or_die(size_t size)
147 void *ret = malloc(size);
151 fprintf(stderr, "out of memory\n");
155 static char *make_name(const char *dirname, const char *subdirname)
157 size_t len = strlen(dirname) + strlen(subdirname) + 2;
158 char *name = malloc_or_die(len);
160 sprintf(name, "%s/%s", dirname, subdirname);
164 static int add_hard_link(char *path, struct stat *s)
168 struct hard_link_data *entry;
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...
175 struct hard_link_data hld = {
180 /* ... and make an osl object out of it. */
181 struct osl_object obj = {
187 * check whether there is a row with the same dev_id and inode values.
189 ret = osl_get_row(table, COL_HLD, &obj, &row);
191 /* Abort on real errors. */
192 if (ret < 0 && ret != -E_OSL_RB_KEY_NOT_FOUND)
195 if (ret < 0) { /* key not found, add a new row to the table. */
196 struct osl_object objs[NUM_HLT_COLUMNS];
198 entry = malloc_or_die(sizeof(*entry));
199 memset(entry, 0, sizeof(*entry));
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;
206 entry->array_size = s->st_nlink; /* that's usually enough */
207 entry->paths = malloc_or_die(entry->array_size * sizeof(char *));
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);
217 } else { /* OK, we have a row, retrieve the hld struct */
218 ret = osl_get_object(table, row, COL_HLD, &obj);
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).
229 * So increase the counter and add the new path to the entry->paths
233 if (entry->num_paths >= entry->array_size) {
235 * New hard links have been created by someone and the
236 * entry->paths array is too small. Double its size.
238 entry->array_size *= 2;
239 entry->paths = realloc(entry->paths,
240 entry->array_size * sizeof(char *));
242 fprintf(stderr, "realloc error. array size: %u\n",
248 entry->paths[entry->num_paths] = path;
254 * Traverse the given directory recursively. Each regular file
255 * with hard link count > 1 is going to be added to the table.
257 static int populate_table(char *dirname)
259 struct dirent *entry;
261 DIR *dir = opendir(dirname);
264 fprintf(stderr, "failed to open dir %s\n", dirname);
265 /* Ignore this error by returning success. */
268 while ((entry = readdir(dir))) {
273 if (!strcmp(entry->d_name, "."))
275 if (!strcmp(entry->d_name, ".."))
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));
286 /* recurse and pass the name of the subdir */
287 ret = populate_table(new_name);
289 if (ret < 0) /* fatal error */
293 if (!S_ISREG(m) || s.st_nlink < 2) {
297 /* regular file with hard links, add it to the table */
298 add_hard_link(new_name, &s);
300 ret = 1; /* success */
306 static int print_row(struct osl_row *row, void *data)
308 struct hard_link_data *hld;
309 struct osl_object obj;
310 int i, ret = osl_get_object(table, row, COL_HLD, &obj);
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]);
325 int main(int argc, char **argv)
329 create_table_or_die(argc, argv);
330 ret = populate_table(argv[1]);
334 * Print results by iterating over all rows and calling print_row() for
337 ret = osl_rbtree_loop(table, COL_HLD, NULL, print_row);
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;