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 /* 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 = (low+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
