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