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