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 "config.h" 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_array(bb->size, sizeof(blk_t), &bb->list); 47 if (retval) { 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 = ((unsigned)low + (unsigned)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
