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 #include "config.h"
9 #include "e2fsck.h"
10
11 /*
12 * This subroutine is called during pass1 to create a directory info
13 * entry. During pass1, the passed-in parent is 0; it will get filled
14 * in during pass2.
15 */
e2fsck_add_dx_dir(e2fsck_t ctx,ext2_ino_t ino,int num_blocks)16 void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks)
17 {
18 struct dx_dir_info *dir;
19 int i, j;
20 errcode_t retval;
21 unsigned long old_size;
22
23 #if 0
24 printf("add_dx_dir_info for inode %lu...\n", ino);
25 #endif
26 if (!ctx->dx_dir_info) {
27 ctx->dx_dir_info_count = 0;
28 ctx->dx_dir_info_size = 100; /* Guess */
29 ctx->dx_dir_info = (struct dx_dir_info *)
30 e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
31 * sizeof (struct dx_dir_info),
32 "directory map");
33 }
34
35 if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
36 old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
37 ctx->dx_dir_info_size += 10;
38 retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
39 sizeof(struct dx_dir_info),
40 &ctx->dx_dir_info);
41 if (retval) {
42 fprintf(stderr, "Couldn't reallocate dx_dir_info "
43 "structure to %d entries\n",
44 ctx->dx_dir_info_size);
45 fatal_error(ctx, 0);
46 ctx->dx_dir_info_size -= 10;
47 return;
48 }
49 }
50
51 /*
52 * Normally, add_dx_dir_info is called with each inode in
53 * sequential order; but once in a while (like when pass 3
54 * needs to recreate the root directory or lost+found
55 * directory) it is called out of order. In those cases, we
56 * need to move the dx_dir_info entries down to make room, since
57 * the dx_dir_info array needs to be sorted by inode number for
58 * get_dx_dir_info()'s sake.
59 */
60 if (ctx->dx_dir_info_count &&
61 ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
62 for (i = ctx->dx_dir_info_count-1; i > 0; i--)
63 if (ctx->dx_dir_info[i-1].ino < ino)
64 break;
65 dir = &ctx->dx_dir_info[i];
66 if (dir->ino != ino)
67 for (j = ctx->dx_dir_info_count++; j > i; j--)
68 ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
69 } else
70 dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
71
72 dir->ino = ino;
73 dir->numblocks = num_blocks;
74 dir->hashversion = 0;
75 dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
76 * sizeof (struct dx_dirblock_info),
77 "dx_block info array");
78
79 }
80
81 /*
82 * get_dx_dir_info() --- given an inode number, try to find the directory
83 * information entry for it.
84 */
e2fsck_get_dx_dir_info(e2fsck_t ctx,ext2_ino_t ino)85 struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
86 {
87 int low, high, mid;
88
89 low = 0;
90 high = ctx->dx_dir_info_count-1;
91 if (!ctx->dx_dir_info)
92 return 0;
93 if (ino == ctx->dx_dir_info[low].ino)
94 return &ctx->dx_dir_info[low];
95 if (ino == ctx->dx_dir_info[high].ino)
96 return &ctx->dx_dir_info[high];
97
98 while (low < high) {
99 mid = (low+high)/2;
100 if (mid == low || mid == high)
101 break;
102 if (ino == ctx->dx_dir_info[mid].ino)
103 return &ctx->dx_dir_info[mid];
104 if (ino < ctx->dx_dir_info[mid].ino)
105 high = mid;
106 else
107 low = mid;
108 }
109 return 0;
110 }
111
112 /*
113 * Free the dx_dir_info structure when it isn't needed any more.
114 */
e2fsck_free_dx_dir_info(e2fsck_t ctx)115 void e2fsck_free_dx_dir_info(e2fsck_t ctx)
116 {
117 int i;
118 struct dx_dir_info *dir;
119
120 if (ctx->dx_dir_info) {
121 dir = ctx->dx_dir_info;
122 for (i=0; i < ctx->dx_dir_info_count; i++,dir++) {
123 if (dir->dx_block) {
124 ext2fs_free_mem(&dir->dx_block);
125 dir->dx_block = 0;
126 }
127 }
128 ext2fs_free_mem(&ctx->dx_dir_info);
129 ctx->dx_dir_info = 0;
130 }
131 ctx->dx_dir_info_size = 0;
132 ctx->dx_dir_info_count = 0;
133 }
134
135 /*
136 * Return the count of number of directories in the dx_dir_info structure
137 */
e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)138 int e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
139 {
140 return ctx->dx_dir_info_count;
141 }
142
143 /*
144 * A simple interator function
145 */
e2fsck_dx_dir_info_iter(e2fsck_t ctx,int * control)146 struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control)
147 {
148 if (*control >= ctx->dx_dir_info_count)
149 return 0;
150
151 return(ctx->dx_dir_info + (*control)++);
152 }
153