blob: 6e5cc10b826ab1294a8b676a4c3e8c3e71dd5b41
1 | /* vi: set sw=4 ts=4: */ |
2 | /* |
3 | * badblocks.c --- routines to manipulate the bad block structure |
4 | * |
5 | * Copyright (C) 1994, 1995, 1996 Theodore Ts'o. |
6 | * |
7 | * %Begin-Header% |
8 | * This file may be redistributed under the terms of the GNU Public |
9 | * License. |
10 | * %End-Header% |
11 | */ |
12 | |
13 | #include <stdio.h> |
14 | #include <string.h> |
15 | #if HAVE_UNISTD_H |
16 | #include <unistd.h> |
17 | #endif |
18 | #include <fcntl.h> |
19 | #include <time.h> |
20 | #if HAVE_SYS_STAT_H |
21 | #include <sys/stat.h> |
22 | #endif |
23 | #if HAVE_SYS_TYPES_H |
24 | #include <sys/types.h> |
25 | #endif |
26 | |
27 | #include "ext2_fs.h" |
28 | #include "ext2fsP.h" |
29 | |
30 | /* |
31 | * Helper function for making a badblocks list |
32 | */ |
33 | static errcode_t make_u32_list(int size, int num, __u32 *list, |
34 | ext2_u32_list *ret) |
35 | { |
36 | ext2_u32_list bb; |
37 | errcode_t retval; |
38 | |
39 | retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_list), &bb); |
40 | if (retval) |
41 | return retval; |
42 | memset(bb, 0, sizeof(struct ext2_struct_u32_list)); |
43 | bb->magic = EXT2_ET_MAGIC_BADBLOCKS_LIST; |
44 | bb->size = size ? size : 10; |
45 | bb->num = num; |
46 | retval = ext2fs_get_mem(bb->size * sizeof(blk_t), &bb->list); |
47 | if (!bb->list) { |
48 | ext2fs_free_mem(&bb); |
49 | return retval; |
50 | } |
51 | if (list) |
52 | memcpy(bb->list, list, bb->size * sizeof(blk_t)); |
53 | else |
54 | memset(bb->list, 0, bb->size * sizeof(blk_t)); |
55 | *ret = bb; |
56 | return 0; |
57 | } |
58 | |
59 | |
60 | /* |
61 | * This procedure creates an empty u32 list. |
62 | */ |
63 | errcode_t ext2fs_u32_list_create(ext2_u32_list *ret, int size) |
64 | { |
65 | return make_u32_list(size, 0, 0, ret); |
66 | } |
67 | |
68 | /* |
69 | * This procedure creates an empty badblocks list. |
70 | */ |
71 | errcode_t ext2fs_badblocks_list_create(ext2_badblocks_list *ret, int size) |
72 | { |
73 | return make_u32_list(size, 0, 0, (ext2_badblocks_list *) ret); |
74 | } |
75 | |
76 | |
77 | /* |
78 | * This procedure copies a badblocks list |
79 | */ |
80 | errcode_t ext2fs_u32_copy(ext2_u32_list src, ext2_u32_list *dest) |
81 | { |
82 | errcode_t retval; |
83 | |
84 | retval = make_u32_list(src->size, src->num, src->list, dest); |
85 | if (retval) |
86 | return retval; |
87 | (*dest)->badblocks_flags = src->badblocks_flags; |
88 | return 0; |
89 | } |
90 | |
91 | errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src, |
92 | ext2_badblocks_list *dest) |
93 | { |
94 | return ext2fs_u32_copy((ext2_u32_list) src, |
95 | (ext2_u32_list *) dest); |
96 | } |
97 | |
98 | /* |
99 | * This procedure frees a badblocks list. |
100 | * |
101 | * (note: moved to closefs.c) |
102 | */ |
103 | |
104 | |
105 | /* |
106 | * This procedure adds a block to a badblocks list. |
107 | */ |
108 | errcode_t ext2fs_u32_list_add(ext2_u32_list bb, __u32 blk) |
109 | { |
110 | errcode_t retval; |
111 | int i, j; |
112 | unsigned long old_size; |
113 | |
114 | EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST); |
115 | |
116 | if (bb->num >= bb->size) { |
117 | old_size = bb->size * sizeof(__u32); |
118 | bb->size += 100; |
119 | retval = ext2fs_resize_mem(old_size, bb->size * sizeof(__u32), |
120 | &bb->list); |
121 | if (retval) { |
122 | bb->size -= 100; |
123 | return retval; |
124 | } |
125 | } |
126 | |
127 | /* |
128 | * Add special case code for appending to the end of the list |
129 | */ |
130 | i = bb->num-1; |
131 | if ((bb->num != 0) && (bb->list[i] == blk)) |
132 | return 0; |
133 | if ((bb->num == 0) || (bb->list[i] < blk)) { |
134 | bb->list[bb->num++] = blk; |
135 | return 0; |
136 | } |
137 | |
138 | j = bb->num; |
139 | for (i=0; i < bb->num; i++) { |
140 | if (bb->list[i] == blk) |
141 | return 0; |
142 | if (bb->list[i] > blk) { |
143 | j = i; |
144 | break; |
145 | } |
146 | } |
147 | for (i=bb->num; i > j; i--) |
148 | bb->list[i] = bb->list[i-1]; |
149 | bb->list[j] = blk; |
150 | bb->num++; |
151 | return 0; |
152 | } |
153 | |
154 | errcode_t ext2fs_badblocks_list_add(ext2_badblocks_list bb, blk_t blk) |
155 | { |
156 | return ext2fs_u32_list_add((ext2_u32_list) bb, (__u32) blk); |
157 | } |
158 | |
159 | /* |
160 | * This procedure finds a particular block is on a badblocks |
161 | * list. |
162 | */ |
163 | int ext2fs_u32_list_find(ext2_u32_list bb, __u32 blk) |
164 | { |
165 | int low, high, mid; |
166 | |
167 | if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST) |
168 | return -1; |
169 | |
170 | if (bb->num == 0) |
171 | return -1; |
172 | |
173 | low = 0; |
174 | high = bb->num-1; |
175 | if (blk == bb->list[low]) |
176 | return low; |
177 | if (blk == bb->list[high]) |
178 | return high; |
179 | |
180 | while (low < high) { |
181 | mid = (low+high)/2; |
182 | if (mid == low || mid == high) |
183 | break; |
184 | if (blk == bb->list[mid]) |
185 | return mid; |
186 | if (blk < bb->list[mid]) |
187 | high = mid; |
188 | else |
189 | low = mid; |
190 | } |
191 | return -1; |
192 | } |
193 | |
194 | /* |
195 | * This procedure tests to see if a particular block is on a badblocks |
196 | * list. |
197 | */ |
198 | int ext2fs_u32_list_test(ext2_u32_list bb, __u32 blk) |
199 | { |
200 | if (ext2fs_u32_list_find(bb, blk) < 0) |
201 | return 0; |
202 | else |
203 | return 1; |
204 | } |
205 | |
206 | int ext2fs_badblocks_list_test(ext2_badblocks_list bb, blk_t blk) |
207 | { |
208 | return ext2fs_u32_list_test((ext2_u32_list) bb, (__u32) blk); |
209 | } |
210 | |
211 | |
212 | /* |
213 | * Remove a block from the badblock list |
214 | */ |
215 | int ext2fs_u32_list_del(ext2_u32_list bb, __u32 blk) |
216 | { |
217 | int remloc, i; |
218 | |
219 | if (bb->num == 0) |
220 | return -1; |
221 | |
222 | remloc = ext2fs_u32_list_find(bb, blk); |
223 | if (remloc < 0) |
224 | return -1; |
225 | |
226 | for (i = remloc; i < bb->num - 1; i++) |
227 | bb->list[i] = bb->list[i+1]; |
228 | bb->num--; |
229 | return 0; |
230 | } |
231 | |
232 | void ext2fs_badblocks_list_del(ext2_u32_list bb, __u32 blk) |
233 | { |
234 | ext2fs_u32_list_del(bb, blk); |
235 | } |
236 | |
237 | errcode_t ext2fs_u32_list_iterate_begin(ext2_u32_list bb, |
238 | ext2_u32_iterate *ret) |
239 | { |
240 | ext2_u32_iterate iter; |
241 | errcode_t retval; |
242 | |
243 | EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST); |
244 | |
245 | retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_iterate), &iter); |
246 | if (retval) |
247 | return retval; |
248 | |
249 | iter->magic = EXT2_ET_MAGIC_BADBLOCKS_ITERATE; |
250 | iter->bb = bb; |
251 | iter->ptr = 0; |
252 | *ret = iter; |
253 | return 0; |
254 | } |
255 | |
256 | errcode_t ext2fs_badblocks_list_iterate_begin(ext2_badblocks_list bb, |
257 | ext2_badblocks_iterate *ret) |
258 | { |
259 | return ext2fs_u32_list_iterate_begin((ext2_u32_list) bb, |
260 | (ext2_u32_iterate *) ret); |
261 | } |
262 | |
263 | |
264 | int ext2fs_u32_list_iterate(ext2_u32_iterate iter, __u32 *blk) |
265 | { |
266 | ext2_u32_list bb; |
267 | |
268 | if (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE) |
269 | return 0; |
270 | |
271 | bb = iter->bb; |
272 | |
273 | if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST) |
274 | return 0; |
275 | |
276 | if (iter->ptr < bb->num) { |
277 | *blk = bb->list[iter->ptr++]; |
278 | return 1; |
279 | } |
280 | *blk = 0; |
281 | return 0; |
282 | } |
283 | |
284 | int ext2fs_badblocks_list_iterate(ext2_badblocks_iterate iter, blk_t *blk) |
285 | { |
286 | return ext2fs_u32_list_iterate((ext2_u32_iterate) iter, |
287 | (__u32 *) blk); |
288 | } |
289 | |
290 | |
291 | void ext2fs_u32_list_iterate_end(ext2_u32_iterate iter) |
292 | { |
293 | if (!iter || (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE)) |
294 | return; |
295 | |
296 | iter->bb = 0; |
297 | ext2fs_free_mem(&iter); |
298 | } |
299 | |
300 | void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter) |
301 | { |
302 | ext2fs_u32_list_iterate_end((ext2_u32_iterate) iter); |
303 | } |
304 | |
305 | |
306 | int ext2fs_u32_list_equal(ext2_u32_list bb1, ext2_u32_list bb2) |
307 | { |
308 | EXT2_CHECK_MAGIC(bb1, EXT2_ET_MAGIC_BADBLOCKS_LIST); |
309 | EXT2_CHECK_MAGIC(bb2, EXT2_ET_MAGIC_BADBLOCKS_LIST); |
310 | |
311 | if (bb1->num != bb2->num) |
312 | return 0; |
313 | |
314 | if (memcmp(bb1->list, bb2->list, bb1->num * sizeof(blk_t)) != 0) |
315 | return 0; |
316 | return 1; |
317 | } |
318 | |
319 | int ext2fs_badblocks_equal(ext2_badblocks_list bb1, ext2_badblocks_list bb2) |
320 | { |
321 | return ext2fs_u32_list_equal((ext2_u32_list) bb1, |
322 | (ext2_u32_list) bb2); |
323 | } |
324 | |
325 | int ext2fs_u32_list_count(ext2_u32_list bb) |
326 | { |
327 | return bb->num; |
328 | } |
329 |