1/*
2 * dirinfo.c --- maintains the directory information table for e2fsck.
3 *
4 * Copyright (C) 1993 Theodore Ts'o.  This file may be redistributed
5 * under the terms of the GNU Public License.
6 */
7
8#undef DIRINFO_DEBUG
9
10#include "config.h"
11#include "e2fsck.h"
12#include <sys/stat.h>
13#include <fcntl.h>
14#include "uuid/uuid.h"
15
16#include "ext2fs/ext2fs.h"
17#include <ext2fs/tdb.h>
18
19struct dir_info_db {
20	int		count;
21	int		size;
22	struct dir_info *array;
23	struct dir_info *last_lookup;
24#ifdef CONFIG_TDB
25	char		*tdb_fn;
26	TDB_CONTEXT	*tdb;
27#endif
28};
29
30struct dir_info_iter {
31	int	i;
32#ifdef CONFIG_TDB
33	TDB_DATA	tdb_iter;
34#endif
35};
36
37struct dir_info_ent {
38	ext2_ino_t		dotdot;	/* Parent according to '..' */
39	ext2_ino_t		parent; /* Parent according to treewalk */
40};
41
42
43static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir);
44
45#ifdef CONFIG_TDB
46static void setup_tdb(e2fsck_t ctx, ext2_ino_t num_dirs)
47{
48	struct dir_info_db	*db = ctx->dir_info;
49	unsigned int		threshold;
50	errcode_t		retval;
51	mode_t			save_umask;
52	char			*tdb_dir, uuid[40];
53	int			fd, enable;
54
55	profile_get_string(ctx->profile, "scratch_files", "directory", 0, 0,
56			   &tdb_dir);
57	profile_get_uint(ctx->profile, "scratch_files",
58			 "numdirs_threshold", 0, 0, &threshold);
59	profile_get_boolean(ctx->profile, "scratch_files",
60			    "dirinfo", 0, 1, &enable);
61
62	if (!enable || !tdb_dir || access(tdb_dir, W_OK) ||
63	    (threshold && num_dirs <= threshold))
64		return;
65
66	retval = ext2fs_get_mem(strlen(tdb_dir) + 64, &db->tdb_fn);
67	if (retval)
68		return;
69
70	uuid_unparse(ctx->fs->super->s_uuid, uuid);
71	sprintf(db->tdb_fn, "%s/%s-dirinfo-XXXXXX", tdb_dir, uuid);
72	save_umask = umask(077);
73	fd = mkstemp(db->tdb_fn);
74	umask(save_umask);
75	if (fd < 0) {
76		db->tdb = NULL;
77		return;
78	}
79
80	if (num_dirs < 99991)
81		num_dirs = 99991; /* largest 5 digit prime */
82
83	db->tdb = tdb_open(db->tdb_fn, num_dirs, TDB_NOLOCK | TDB_NOSYNC,
84			   O_RDWR | O_CREAT | O_TRUNC, 0600);
85	close(fd);
86}
87#endif
88
89static void setup_db(e2fsck_t ctx)
90{
91	struct dir_info_db	*db;
92	ext2_ino_t		num_dirs;
93	errcode_t		retval;
94
95	db = (struct dir_info_db *)
96		e2fsck_allocate_memory(ctx, sizeof(struct dir_info_db),
97				       "directory map db");
98	db->count = db->size = 0;
99	db->array = 0;
100
101	ctx->dir_info = db;
102
103	retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
104	if (retval)
105		num_dirs = 1024;	/* Guess */
106
107#ifdef CONFIG_TDB
108	setup_tdb(ctx, num_dirs);
109
110	if (db->tdb) {
111#ifdef DIRINFO_DEBUG
112		printf("Note: using tdb!\n");
113#endif
114		return;
115	}
116#endif
117
118	db->size = num_dirs + 10;
119	db->array  = (struct dir_info *)
120		e2fsck_allocate_memory(ctx, db->size
121				       * sizeof (struct dir_info),
122				       "directory map");
123}
124
125/*
126 * This subroutine is called during pass1 to create a directory info
127 * entry.  During pass1, the passed-in parent is 0; it will get filled
128 * in during pass2.
129 */
130void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
131{
132	struct dir_info		*dir, *old_array;
133	int			i, j;
134	errcode_t		retval;
135	unsigned long		old_size;
136
137#ifdef DIRINFO_DEBUG
138	printf("add_dir_info for inode (%lu, %lu)...\n", ino, parent);
139#endif
140	if (!ctx->dir_info)
141		setup_db(ctx);
142
143	if (ctx->dir_info->count >= ctx->dir_info->size) {
144		old_size = ctx->dir_info->size * sizeof(struct dir_info);
145		ctx->dir_info->size += 10;
146		old_array = ctx->dir_info->array;
147		retval = ext2fs_resize_mem(old_size, ctx->dir_info->size *
148					   sizeof(struct dir_info),
149					   &ctx->dir_info->array);
150		if (retval) {
151			fprintf(stderr, "Couldn't reallocate dir_info "
152				"structure to %d entries\n",
153				ctx->dir_info->size);
154			fatal_error(ctx, 0);
155			ctx->dir_info->size -= 10;
156			return;
157		}
158		if (old_array != ctx->dir_info->array)
159			ctx->dir_info->last_lookup = NULL;
160	}
161
162#ifdef CONFIG_TDB
163	if (ctx->dir_info->tdb) {
164		struct dir_info ent;
165
166		ent.ino = ino;
167		ent.parent = parent;
168		ent.dotdot = parent;
169		e2fsck_put_dir_info(ctx, &ent);
170		return;
171	}
172#endif
173
174	/*
175	 * Normally, add_dir_info is called with each inode in
176	 * sequential order; but once in a while (like when pass 3
177	 * needs to recreate the root directory or lost+found
178	 * directory) it is called out of order.  In those cases, we
179	 * need to move the dir_info entries down to make room, since
180	 * the dir_info array needs to be sorted by inode number for
181	 * get_dir_info()'s sake.
182	 */
183	if (ctx->dir_info->count &&
184	    ctx->dir_info->array[ctx->dir_info->count-1].ino >= ino) {
185		for (i = ctx->dir_info->count-1; i > 0; i--)
186			if (ctx->dir_info->array[i-1].ino < ino)
187				break;
188		dir = &ctx->dir_info->array[i];
189		if (dir->ino != ino)
190			for (j = ctx->dir_info->count++; j > i; j--)
191				ctx->dir_info->array[j] = ctx->dir_info->array[j-1];
192	} else
193		dir = &ctx->dir_info->array[ctx->dir_info->count++];
194
195	dir->ino = ino;
196	dir->dotdot = parent;
197	dir->parent = parent;
198}
199
200/*
201 * get_dir_info() --- given an inode number, try to find the directory
202 * information entry for it.
203 */
204static struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
205{
206	struct dir_info_db	*db = ctx->dir_info;
207	int			low, high, mid;
208
209	if (!db)
210		return 0;
211
212#ifdef DIRINFO_DEBUG
213	printf("e2fsck_get_dir_info %d...", ino);
214#endif
215
216#ifdef CONFIG_TDB
217	if (db->tdb) {
218		static struct dir_info	ret_dir_info;
219		TDB_DATA key, data;
220		struct dir_info_ent	*buf;
221
222		key.dptr = (unsigned char *) &ino;
223		key.dsize = sizeof(ext2_ino_t);
224
225		data = tdb_fetch(db->tdb, key);
226		if (!data.dptr) {
227			if (tdb_error(db->tdb) != TDB_ERR_NOEXIST)
228				printf("fetch failed: %s\n",
229				       tdb_errorstr(db->tdb));
230			return 0;
231		}
232
233		buf = (struct dir_info_ent *) data.dptr;
234		ret_dir_info.ino = ino;
235		ret_dir_info.dotdot = buf->dotdot;
236		ret_dir_info.parent = buf->parent;
237#ifdef DIRINFO_DEBUG
238		printf("(%d,%d,%d)\n", ino, buf->dotdot, buf->parent);
239#endif
240		free(data.dptr);
241		return &ret_dir_info;
242	}
243#endif
244
245	if (db->last_lookup && db->last_lookup->ino == ino)
246		return db->last_lookup;
247
248	low = 0;
249	high = ctx->dir_info->count-1;
250	if (ino == ctx->dir_info->array[low].ino) {
251#ifdef DIRINFO_DEBUG
252		printf("(%d,%d,%d)\n", ino,
253		       ctx->dir_info->array[low].dotdot,
254		       ctx->dir_info->array[low].parent);
255#endif
256		return &ctx->dir_info->array[low];
257	}
258	if (ino == ctx->dir_info->array[high].ino) {
259#ifdef DIRINFO_DEBUG
260		printf("(%d,%d,%d)\n", ino,
261		       ctx->dir_info->array[high].dotdot,
262		       ctx->dir_info->array[high].parent);
263#endif
264		return &ctx->dir_info->array[high];
265	}
266
267	while (low < high) {
268		mid = (low+high)/2;
269		if (mid == low || mid == high)
270			break;
271		if (ino == ctx->dir_info->array[mid].ino) {
272#ifdef DIRINFO_DEBUG
273			printf("(%d,%d,%d)\n", ino,
274			       ctx->dir_info->array[mid].dotdot,
275			       ctx->dir_info->array[mid].parent);
276#endif
277			return &ctx->dir_info->array[mid];
278		}
279		if (ino < ctx->dir_info->array[mid].ino)
280			high = mid;
281		else
282			low = mid;
283	}
284	return 0;
285}
286
287static void e2fsck_put_dir_info(e2fsck_t ctx EXT2FS_NO_TDB_UNUSED,
288				struct dir_info *dir EXT2FS_NO_TDB_UNUSED)
289{
290#ifdef CONFIG_TDB
291	struct dir_info_db	*db = ctx->dir_info;
292	struct dir_info_ent	buf;
293	TDB_DATA		key, data;
294#endif
295
296#ifdef DIRINFO_DEBUG
297	printf("e2fsck_put_dir_info (%d, %d, %d)...", dir->ino, dir->dotdot,
298	       dir->parent);
299#endif
300
301#ifdef CONFIG_TDB
302	if (!db->tdb)
303		return;
304
305	buf.parent = dir->parent;
306	buf.dotdot = dir->dotdot;
307
308	key.dptr = (unsigned char *) &dir->ino;
309	key.dsize = sizeof(ext2_ino_t);
310	data.dptr = (unsigned char *) &buf;
311	data.dsize = sizeof(buf);
312
313	if (tdb_store(db->tdb, key, data, TDB_REPLACE) == -1) {
314		printf("store failed: %s\n", tdb_errorstr(db->tdb));
315	}
316#endif
317}
318
319/*
320 * Free the dir_info structure when it isn't needed any more.
321 */
322void e2fsck_free_dir_info(e2fsck_t ctx)
323{
324	if (ctx->dir_info) {
325#ifdef CONFIG_TDB
326		if (ctx->dir_info->tdb)
327			tdb_close(ctx->dir_info->tdb);
328		if (ctx->dir_info->tdb_fn) {
329			unlink(ctx->dir_info->tdb_fn);
330			free(ctx->dir_info->tdb_fn);
331		}
332#endif
333		if (ctx->dir_info->array)
334			ext2fs_free_mem(&ctx->dir_info->array);
335		ctx->dir_info->array = 0;
336		ctx->dir_info->size = 0;
337		ctx->dir_info->count = 0;
338		ext2fs_free_mem(&ctx->dir_info);
339		ctx->dir_info = 0;
340	}
341}
342
343/*
344 * Return the count of number of directories in the dir_info structure
345 */
346int e2fsck_get_num_dirinfo(e2fsck_t ctx)
347{
348	return ctx->dir_info ? ctx->dir_info->count : 0;
349}
350
351struct dir_info_iter *e2fsck_dir_info_iter_begin(e2fsck_t ctx)
352{
353	struct dir_info_iter *iter;
354
355	iter = e2fsck_allocate_memory(ctx, sizeof(struct dir_info_iter),
356				      "dir_info iterator");
357
358#ifdef CONFIG_TDB
359	if (ctx->dir_info->tdb)
360		iter->tdb_iter = tdb_firstkey(ctx->dir_info->tdb);
361#endif
362
363	return iter;
364}
365
366void e2fsck_dir_info_iter_end(e2fsck_t ctx EXT2FS_ATTR((unused)),
367			      struct dir_info_iter *iter)
368{
369#ifdef CONFIG_TDB
370	free(iter->tdb_iter.dptr);
371#endif
372	ext2fs_free_mem(&iter);
373}
374
375/*
376 * A simple interator function
377 */
378struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, struct dir_info_iter *iter)
379{
380	if (!ctx->dir_info || !iter)
381		return 0;
382
383#ifdef CONFIG_TDB
384	if (ctx->dir_info->tdb) {
385		static struct dir_info ret_dir_info;
386		struct dir_info_ent *buf;
387		TDB_DATA data, key;
388
389		if (iter->tdb_iter.dptr == 0)
390			return 0;
391		key = iter->tdb_iter;
392		data = tdb_fetch(ctx->dir_info->tdb, key);
393		if (!data.dptr) {
394			printf("iter fetch failed: %s\n",
395			       tdb_errorstr(ctx->dir_info->tdb));
396			return 0;
397		}
398		buf = (struct dir_info_ent *) data.dptr;
399		ret_dir_info.ino = *((ext2_ino_t *) iter->tdb_iter.dptr);
400		ret_dir_info.dotdot = buf->dotdot;
401		ret_dir_info.parent = buf->parent;
402		iter->tdb_iter = tdb_nextkey(ctx->dir_info->tdb, key);
403		free(key.dptr);
404		free(data.dptr);
405		return &ret_dir_info;
406	}
407#endif
408
409	if (iter->i >= ctx->dir_info->count)
410		return 0;
411
412#ifdef DIRINFO_DEBUG
413	printf("iter(%d, %d, %d)...", ctx->dir_info->array[iter->i].ino,
414	       ctx->dir_info->array[iter->i].dotdot,
415	       ctx->dir_info->array[iter->i].parent);
416#endif
417	ctx->dir_info->last_lookup = ctx->dir_info->array + iter->i++;
418	return(ctx->dir_info->last_lookup);
419}
420
421/*
422 * This function only sets the parent pointer, and requires that
423 * dirinfo structure has already been created.
424 */
425int e2fsck_dir_info_set_parent(e2fsck_t ctx, ext2_ino_t ino,
426			       ext2_ino_t parent)
427{
428	struct dir_info *p;
429
430	p = e2fsck_get_dir_info(ctx, ino);
431	if (!p)
432		return 1;
433	p->parent = parent;
434	e2fsck_put_dir_info(ctx, p);
435	return 0;
436}
437
438/*
439 * This function only sets the dot dot pointer, and requires that
440 * dirinfo structure has already been created.
441 */
442int e2fsck_dir_info_set_dotdot(e2fsck_t ctx, ext2_ino_t ino,
443			       ext2_ino_t dotdot)
444{
445	struct dir_info *p;
446
447	p = e2fsck_get_dir_info(ctx, ino);
448	if (!p)
449		return 1;
450	p->dotdot = dotdot;
451	e2fsck_put_dir_info(ctx, p);
452	return 0;
453}
454
455/*
456 * This function only sets the parent pointer, and requires that
457 * dirinfo structure has already been created.
458 */
459int e2fsck_dir_info_get_parent(e2fsck_t ctx, ext2_ino_t ino,
460			       ext2_ino_t *parent)
461{
462	struct dir_info *p;
463
464	p = e2fsck_get_dir_info(ctx, ino);
465	if (!p)
466		return 1;
467	*parent = p->parent;
468	return 0;
469}
470
471/*
472 * This function only sets the dot dot pointer, and requires that
473 * dirinfo structure has already been created.
474 */
475int e2fsck_dir_info_get_dotdot(e2fsck_t ctx, ext2_ino_t ino,
476			       ext2_ino_t *dotdot)
477{
478	struct dir_info *p;
479
480	p = e2fsck_get_dir_info(ctx, ino);
481	if (!p)
482		return 1;
483	*dotdot = p->dotdot;
484	return 0;
485}
486
487