]>
Commit | Line | Data |
---|---|---|
8fdc9985 TT |
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 | ||
d1154eb4 | 8 | #include "config.h" |
8fdc9985 | 9 | #include "e2fsck.h" |
8fdc9985 TT |
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 | |
efc6f628 | 14 | * in during pass2. |
8fdc9985 | 15 | */ |
28b44ef0 GKB |
16 | void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, struct ext2_inode *inode, |
17 | int num_blocks) | |
8fdc9985 TT |
18 | { |
19 | struct dx_dir_info *dir; | |
74fbba1f | 20 | ext2_ino_t i, j; |
8fdc9985 TT |
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 | } | |
efc6f628 | 35 | |
8fdc9985 TT |
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), | |
c4e3d3f3 | 41 | &ctx->dx_dir_info); |
8fdc9985 | 42 | if (retval) { |
e9a5c6e3 | 43 | fprintf(stderr, "Couldn't reallocate dx_dir_info " |
74fbba1f | 44 | "structure to %u entries\n", |
e9a5c6e3 TT |
45 | ctx->dx_dir_info_size); |
46 | fatal_error(ctx, 0); | |
8fdc9985 TT |
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]; | |
efc6f628 | 67 | if (dir->ino != ino) |
8fdc9985 TT |
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++]; | |
efc6f628 | 72 | |
8fdc9985 TT |
73 | dir->ino = ino; |
74 | dir->numblocks = num_blocks; | |
75 | dir->hashversion = 0; | |
abeb84e3 | 76 | dir->casefolded_hash = !!(inode->i_flags & EXT4_CASEFOLD_FL); |
8fdc9985 TT |
77 | dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks |
78 | * sizeof (struct dx_dirblock_info), | |
79 | "dx_block info array"); | |
8fdc9985 TT |
80 | } |
81 | ||
82 | /* | |
83 | * get_dx_dir_info() --- given an inode number, try to find the directory | |
84 | * information entry for it. | |
85 | */ | |
86 | struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino) | |
87 | { | |
74fbba1f | 88 | ext2_ino_t low, high, mid; |
8fdc9985 TT |
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) { | |
74fbba1f AD |
100 | /* sum may overflow, but result will fit into mid again */ |
101 | mid = (unsigned long long)(low + high) / 2; | |
8fdc9985 TT |
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 | */ | |
117 | void e2fsck_free_dx_dir_info(e2fsck_t ctx) | |
118 | { | |
8fdc9985 | 119 | struct dx_dir_info *dir; |
74fbba1f | 120 | ext2_ino_t i; |
efc6f628 | 121 | |
8fdc9985 TT |
122 | if (ctx->dx_dir_info) { |
123 | dir = ctx->dx_dir_info; | |
23f75f6e | 124 | for (i=0; i < ctx->dx_dir_info_count; i++,dir++) { |
8fdc9985 | 125 | if (dir->dx_block) { |
c4e3d3f3 | 126 | ext2fs_free_mem(&dir->dx_block); |
8fdc9985 TT |
127 | dir->dx_block = 0; |
128 | } | |
129 | } | |
c4e3d3f3 | 130 | ext2fs_free_mem(&ctx->dx_dir_info); |
8fdc9985 TT |
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 | */ | |
382ed4a1 | 140 | ext2_ino_t e2fsck_get_num_dx_dirinfo(e2fsck_t ctx) |
8fdc9985 TT |
141 | { |
142 | return ctx->dx_dir_info_count; | |
143 | } | |
144 | ||
145 | /* | |
146 | * A simple interator function | |
147 | */ | |
382ed4a1 | 148 | struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, ext2_ino_t *control) |
8fdc9985 TT |
149 | { |
150 | if (*control >= ctx->dx_dir_info_count) | |
151 | return 0; | |
152 | ||
382ed4a1 | 153 | return ctx->dx_dir_info + (*control)++; |
8fdc9985 | 154 | } |