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