2 * dirinfo.c --- maintains the directory information table for e2fsck.
4 * Copyright (C) 1993 Theodore Ts'o. This file may be redistributed
5 * under the terms of the GNU Public License.
13 * This subroutine is called during pass1 to create a directory info
14 * entry. During pass1, the passed-in parent is 0; it will get filled
17 void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, struct ext2_inode *inode,
20 struct dx_dir_info *dir;
23 unsigned long old_size;
26 printf("add_dx_dir_info for inode %lu...\n", ino);
28 if (!ctx->dx_dir_info) {
29 ctx->dx_dir_info_count = 0;
30 ctx->dx_dir_info_size = 100; /* Guess */
31 ctx->dx_dir_info = (struct dx_dir_info *)
32 e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
33 * sizeof (struct dx_dir_info),
37 if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
38 old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
39 ctx->dx_dir_info_size += 10;
40 retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
41 sizeof(struct dx_dir_info),
44 fprintf(stderr, "Couldn't reallocate dx_dir_info "
45 "structure to %u entries\n",
46 ctx->dx_dir_info_size);
48 ctx->dx_dir_info_size -= 10;
54 * Normally, add_dx_dir_info is called with each inode in
55 * sequential order; but once in a while (like when pass 3
56 * needs to recreate the root directory or lost+found
57 * directory) it is called out of order. In those cases, we
58 * need to move the dx_dir_info entries down to make room, since
59 * the dx_dir_info array needs to be sorted by inode number for
60 * get_dx_dir_info()'s sake.
62 if (ctx->dx_dir_info_count &&
63 ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
64 for (i = ctx->dx_dir_info_count-1; i > 0; i--)
65 if (ctx->dx_dir_info[i-1].ino < ino)
67 dir = &ctx->dx_dir_info[i];
69 for (j = ctx->dx_dir_info_count++; j > i; j--)
70 ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
72 dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
75 dir->numblocks = num_blocks;
77 dir->casefolded_hash = !!(inode->i_flags & EXT4_CASEFOLD_FL);
78 dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
79 * sizeof (struct dx_dirblock_info),
80 "dx_block info array");
84 * Merge two sorted dir info to @dest
86 void e2fsck_merge_dx_dir(e2fsck_t global_ctx, e2fsck_t thread_ctx)
88 struct dx_dir_info *src_array = thread_ctx->dx_dir_info;
89 struct dx_dir_info *dest_array = global_ctx->dx_dir_info;
90 size_t size_dx_info = sizeof(struct dx_dir_info);
91 ext2_ino_t size = global_ctx->dx_dir_info_size;
92 ext2_ino_t src_count = thread_ctx->dx_dir_info_count;
93 ext2_ino_t dest_count = global_ctx->dx_dir_info_count;
94 ext2_ino_t total_count = src_count + dest_count;
95 struct dx_dir_info *array;
96 struct dx_dir_info *array_ptr;
97 ext2_ino_t src_index = 0, dest_index = 0;
99 if (thread_ctx->dx_dir_info_count == 0)
102 if (size < total_count)
105 array = e2fsck_allocate_memory(global_ctx, size * size_dx_info,
109 * This can be improved by binary search and memcpy, but codes
110 * would be more complex. And if the groups distributed to each
111 * thread are strided, this implementation won't be too bad
112 * comparing to the optimiztion.
114 while (src_index < src_count || dest_index < dest_count) {
115 if (src_index >= src_count) {
116 memcpy(array_ptr, &dest_array[dest_index],
117 (dest_count - dest_index) * size_dx_info);
120 if (dest_index >= dest_count) {
121 memcpy(array_ptr, &src_array[src_index],
122 (src_count - src_index) * size_dx_info);
125 if (src_array[src_index].ino < dest_array[dest_index].ino) {
126 *array_ptr = src_array[src_index];
129 assert(src_array[src_index].ino >
130 dest_array[dest_index].ino);
131 *array_ptr = dest_array[dest_index];
137 if (global_ctx->dx_dir_info)
138 ext2fs_free_mem(&global_ctx->dx_dir_info);
139 if (thread_ctx->dx_dir_info)
140 ext2fs_free_mem(&thread_ctx->dx_dir_info);
141 global_ctx->dx_dir_info = array;
142 global_ctx->dx_dir_info_size = size;
143 global_ctx->dx_dir_info_count = total_count;
147 * get_dx_dir_info() --- given an inode number, try to find the directory
148 * information entry for it.
150 struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
152 ext2_ino_t low, high, mid;
155 high = ctx->dx_dir_info_count-1;
156 if (!ctx->dx_dir_info)
158 if (ino == ctx->dx_dir_info[low].ino)
159 return &ctx->dx_dir_info[low];
160 if (ino == ctx->dx_dir_info[high].ino)
161 return &ctx->dx_dir_info[high];
164 /* sum may overflow, but result will fit into mid again */
165 mid = (unsigned long long)(low + high) / 2;
166 if (mid == low || mid == high)
168 if (ino == ctx->dx_dir_info[mid].ino)
169 return &ctx->dx_dir_info[mid];
170 if (ino < ctx->dx_dir_info[mid].ino)
179 * Free the dx_dir_info structure when it isn't needed any more.
181 void e2fsck_free_dx_dir_info(e2fsck_t ctx)
183 struct dx_dir_info *dir;
186 if (ctx->dx_dir_info) {
187 dir = ctx->dx_dir_info;
188 for (i=0; i < ctx->dx_dir_info_count; i++,dir++) {
190 ext2fs_free_mem(&dir->dx_block);
194 ext2fs_free_mem(&ctx->dx_dir_info);
195 ctx->dx_dir_info = 0;
197 ctx->dx_dir_info_size = 0;
198 ctx->dx_dir_info_count = 0;
202 * Return the count of number of directories in the dx_dir_info structure
204 ext2_ino_t e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
206 return ctx->dx_dir_info_count;
210 * A simple interator function
212 struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, ext2_ino_t *control)
214 if (*control >= ctx->dx_dir_info_count)
217 return ctx->dx_dir_info + (*control)++;