badblocks.c revision a4aff9ca5bcc3df76dcb3d49765674feba3d7654
15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * badblocks.c --- routines to manipulate the bad block structure 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 1994, 1995, 1996 Theodore Ts'o. 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * %Begin-Header% 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This file may be redistributed under the terms of the GNU Library 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * General Public License, version 2. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * %End-Header% 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <stdio.h> 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <string.h> 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if HAVE_UNISTD_H 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <unistd.h> 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <fcntl.h> 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <time.h> 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if HAVE_SYS_STAT_H 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <sys/stat.h> 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if HAVE_SYS_TYPES_H 2302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch#include <sys/types.h> 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "ext2_fs.h" 27f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#include "ext2fsP.h" 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 29bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)/* 307757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch * Helper function for making a badblocks list 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 32c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)static errcode_t make_u32_list(int size, int num, __u32 *list, 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ext2_u32_list *ret) 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ext2_u32_list bb; 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) errcode_t retval; 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_list), &bb); 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (retval) 40c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles) return retval; 4109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) memset(bb, 0, sizeof(struct ext2_struct_u32_list)); 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bb->magic = EXT2_ET_MAGIC_BADBLOCKS_LIST; 4302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch bb->size = size ? size : 10; 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bb->num = num; 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) retval = ext2fs_get_array(bb->size, sizeof(blk_t), &bb->list); 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (retval) { 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ext2fs_free_mem(&bb); 4809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return retval; 4909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (list) 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memcpy(bb->list, list, bb->size * sizeof(blk_t)); 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memset(bb->list, 0, bb->size * sizeof(blk_t)); 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *ret = bb; 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 5609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This procedure creates an empty u32 list. 61c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles) */ 62errcode_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 */ 70errcode_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 */ 79errcode_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 90errcode_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 */ 107errcode_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 153errcode_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 */ 162int 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 */ 197int 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 205int 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 */ 214int 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 231void ext2fs_badblocks_list_del(ext2_u32_list bb, __u32 blk) 232{ 233 ext2fs_u32_list_del(bb, blk); 234} 235 236errcode_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 255errcode_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 263int 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 283int 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 290void 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 299void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter) 300{ 301 ext2fs_u32_list_iterate_end((ext2_u32_iterate) iter); 302} 303 304 305int 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 318int 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 324int ext2fs_u32_list_count(ext2_u32_list bb) 325{ 326 return bb->num; 327} 328