lib/ext2fs/badblocks.c

   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 }