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