1/* vi: set sw=4 ts=4: */ 2/* 3 * badblocks.c --- routines to manipulate the bad block structure 4 * 5 * Copyright (C) 1994, 1995, 1996 Theodore Ts'o. 6 * 7 * %Begin-Header% 8 * This file may be redistributed under the terms of the GNU Public 9 * License. 10 * %End-Header% 11 */ 12 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 */ 33static 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_mem(bb->size * sizeof(blk_t), &bb->list); 47 if (!bb->list) { 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 */ 63errcode_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 */ 71errcode_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 */ 80errcode_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 91errcode_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 */ 108errcode_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 154errcode_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 */ 163int 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 = (low+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 */ 198int 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 206int 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 */ 215int 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 232void ext2fs_badblocks_list_del(ext2_u32_list bb, __u32 blk) 233{ 234 ext2fs_u32_list_del(bb, blk); 235} 236 237errcode_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 256errcode_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 264int 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 284int 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 291void 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 300void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter) 301{ 302 ext2fs_u32_list_iterate_end((ext2_u32_iterate) iter); 303} 304 305 306int 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 319int 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 325int ext2fs_u32_list_count(ext2_u32_list bb) 326{ 327 return bb->num; 328} 329