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 Library
   8  * General Public License, version 2.
   9  * %End-Header%
  10  */
  11
  12 #include "config.h"
  13 #include <stdio.h>
  14 #include <assert.h>
  15 #include <string.h>
  16 #if HAVE_UNISTD_H
  17 #include <unistd.h>
  18 #endif
  19 #include <fcntl.h>
  20 #include <time.h>
  21 #if HAVE_SYS_STAT_H
  22 #include <sys/stat.h>
  23 #endif
  24 #if HAVE_SYS_TYPES_H
  25 #include <sys/types.h>
  26 #endif
  27
  28 #include "ext2_fs.h"
  29 #include "ext2fsP.h"
  30
  31 /*
  32  * Helper function for making a badblocks list
  33  */
  34 static errcode_t make_u32_list(int size, int num, __u32 *list,
  35                                ext2_u32_list *ret)
  36 {
  37         ext2_u32_list   bb;
  38         errcode_t       retval;
  39
  40         retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_list), &bb);
  41         if (retval)
  42                 return retval;
  43         memset(bb, 0, sizeof(struct ext2_struct_u32_list));
  44         bb->magic = EXT2_ET_MAGIC_BADBLOCKS_LIST;
  45         bb->size = size ? size : 10;
  46         bb->num = num;
  47         retval = ext2fs_get_array(bb->size, sizeof(blk_t), &bb->list);
  48         if (retval) {
  49                 ext2fs_free_mem(&bb);
  50                 return retval;
  51         }
  52         if (list)
  53                 memcpy(bb->list, list, bb->size * sizeof(blk_t));
  54         else
  55                 memset(bb->list, 0, bb->size * sizeof(blk_t));
  56         *ret = bb;
  57         return 0;
  58 }
  59
  60 static inline int insert_ok(blk_t *array, int cnt, blk_t new)
  61 {
  62         return (cnt == 0 || array[cnt - 1] != new);
  63 }
  64
  65 /*
  66  * Merge list from src to dest
  67  */
  68 static errcode_t merge_u32_list(ext2_u32_list src, ext2_u32_list dest)
  69 {
  70         errcode_t        retval;
  71         int              src_count = src->num;
  72         int              dest_count = dest->num;
  73         int              size = src_count + dest_count;
  74         int              size_entry = sizeof(blk_t);
  75         blk_t           *array;
  76         blk_t           *src_array = src->list;
  77         blk_t           *dest_array = dest->list;
  78         int              src_index = 0;
  79         int              dest_index = 0;
  80         int              uniq_cnt = 0;
  81
  82         if (src->num == 0)
  83                 return 0;
  84
  85         retval = ext2fs_get_array(size, size_entry, &array);
  86         if (retval)
  87                 return retval;
  88
  89         /*
  90          * It is possible that src list and dest list could be
  91          * duplicated when merging badblocks.
  92          */
  93         while (src_index < src_count || dest_index < dest_count) {
  94                 if (src_index >= src_count) {
  95                         for (; dest_index < dest_count; dest_index++)
  96                                 if (insert_ok(array, uniq_cnt, dest_array[dest_index]))
  97                                         array[uniq_cnt++] = dest_array[dest_index];
  98                         break;
  99                 }
 100                 if (dest_index >= dest_count) {
 101                         for (; src_index < src_count; src_index++)
 102                                 if (insert_ok(array, uniq_cnt, src_array[src_index]))
 103                                         array[uniq_cnt++] = src_array[src_index];
 104                         break;
 105                 }
 106                 if (src_array[src_index] < dest_array[dest_index]) {
 107                         if (insert_ok(array, uniq_cnt, src_array[src_index]))
 108                                 array[uniq_cnt++] = src_array[src_index];
 109                         src_index++;
 110                 } else if (src_array[src_index] > dest_array[dest_index]) {
 111                         if (insert_ok(array, uniq_cnt, dest_array[dest_index]))
 112                                 array[uniq_cnt++] = dest_array[dest_index];
 113                         dest_index++;
 114                 } else {
 115                         if (insert_ok(array, uniq_cnt, dest_array[dest_index]))
 116                                 array[uniq_cnt++] = dest_array[dest_index];
 117                         src_index++;
 118                         dest_index++;
 119                 }
 120         }
 121
 122         ext2fs_free_mem(&dest->list);
 123         dest->list = array;
 124         dest->num = uniq_cnt;
 125         dest->size = size;
 126         return 0;
 127 }
 128
 129
 130 /*
 131  * This procedure creates an empty u32 list.
 132  */
 133 errcode_t ext2fs_u32_list_create(ext2_u32_list *ret, int size)
 134 {
 135         return make_u32_list(size, 0, 0, ret);
 136 }
 137
 138 /*
 139  * This procedure creates an empty badblocks list.
 140  */
 141 errcode_t ext2fs_badblocks_list_create(ext2_badblocks_list *ret, int size)
 142 {
 143         return make_u32_list(size, 0, 0, (ext2_badblocks_list *) ret);
 144 }
 145
 146
 147 /*
 148  * This procedure copies a badblocks list
 149  */
 150 errcode_t ext2fs_u32_copy(ext2_u32_list src, ext2_u32_list *dest)
 151 {
 152         return make_u32_list(src->size, src->num, src->list, dest);
 153 }
 154
 155 errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
 156                                 ext2_badblocks_list *dest)
 157 {
 158         return ext2fs_u32_copy((ext2_u32_list) src,
 159                                (ext2_u32_list *) dest);
 160 }
 161
 162 errcode_t ext2fs_badblocks_merge(ext2_badblocks_list src,
 163                                  ext2_badblocks_list dest)
 164 {
 165         return merge_u32_list((ext2_u32_list) src,
 166                               (ext2_u32_list) dest);
 167 }
 168
 169 /*
 170  * This procedure frees a badblocks list.
 171  *
 172  * (note: moved to closefs.c)
 173  */
 174
 175
 176 /*
 177  * This procedure adds a block to a badblocks list.
 178  */
 179 errcode_t ext2fs_u32_list_add(ext2_u32_list bb, __u32 blk)
 180 {
 181         errcode_t       retval;
 182         int             i, j;
 183         unsigned long   old_size;
 184
 185         EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 186
 187         if (bb->num >= bb->size) {
 188                 old_size = bb->size * sizeof(__u32);
 189                 bb->size += 100;
 190                 retval = ext2fs_resize_mem(old_size, bb->size * sizeof(__u32),
 191                                            &bb->list);
 192                 if (retval) {
 193                         bb->size -= 100;
 194                         return retval;
 195                 }
 196         }
 197
 198         /*
 199          * Add special case code for appending to the end of the list
 200          */
 201         i = bb->num-1;
 202         if ((bb->num != 0) && (bb->list[i] == blk))
 203                 return 0;
 204         if ((bb->num == 0) || (bb->list[i] < blk)) {
 205                 bb->list[bb->num++] = blk;
 206                 return 0;
 207         }
 208
 209         j = bb->num;
 210         for (i=0; i < bb->num; i++) {
 211                 if (bb->list[i] == blk)
 212                         return 0;
 213                 if (bb->list[i] > blk) {
 214                         j = i;
 215                         break;
 216                 }
 217         }
 218         for (i=bb->num; i > j; i--)
 219                 bb->list[i] = bb->list[i-1];
 220         bb->list[j] = blk;
 221         bb->num++;
 222         return 0;
 223 }
 224
 225 errcode_t ext2fs_badblocks_list_add(ext2_badblocks_list bb, blk_t blk)
 226 {
 227         return ext2fs_u32_list_add((ext2_u32_list) bb, (__u32) blk);
 228 }
 229
 230 /*
 231  * This procedure finds a particular block is on a badblocks
 232  * list.
 233  */
 234 int ext2fs_u32_list_find(ext2_u32_list bb, __u32 blk)
 235 {
 236         int     low, high, mid;
 237
 238         if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST)
 239                 return -1;
 240
 241         if (bb->num == 0)
 242                 return -1;
 243
 244         low = 0;
 245         high = bb->num-1;
 246         if (blk == bb->list[low])
 247                 return low;
 248         if (blk == bb->list[high])
 249                 return high;
 250
 251         while (low < high) {
 252                 mid = ((unsigned)low + (unsigned)high)/2;
 253                 if (mid == low || mid == high)
 254                         break;
 255                 if (blk == bb->list[mid])
 256                         return mid;
 257                 if (blk < bb->list[mid])
 258                         high = mid;
 259                 else
 260                         low = mid;
 261         }
 262         return -1;
 263 }
 264
 265 /*
 266  * This procedure tests to see if a particular block is on a badblocks
 267  * list.
 268  */
 269 int ext2fs_u32_list_test(ext2_u32_list bb, __u32 blk)
 270 {
 271         if (ext2fs_u32_list_find(bb, blk) < 0)
 272                 return 0;
 273         else
 274                 return 1;
 275 }
 276
 277 int ext2fs_badblocks_list_test(ext2_badblocks_list bb, blk_t blk)
 278 {
 279         return ext2fs_u32_list_test((ext2_u32_list) bb, (__u32) blk);
 280 }
 281
 282
 283 /*
 284  * Remove a block from the badblock list
 285  */
 286 int ext2fs_u32_list_del(ext2_u32_list bb, __u32 blk)
 287 {
 288         int     remloc, i;
 289
 290         if (bb->num == 0)
 291                 return -1;
 292
 293         remloc = ext2fs_u32_list_find(bb, blk);
 294         if (remloc < 0)
 295                 return -1;
 296
 297         for (i = remloc ; i < bb->num-1; i++)
 298                 bb->list[i] = bb->list[i+1];
 299         bb->num--;
 300         return 0;
 301 }
 302
 303 void ext2fs_badblocks_list_del(ext2_u32_list bb, __u32 blk)
 304 {
 305         ext2fs_u32_list_del(bb, blk);
 306 }
 307
 308 errcode_t ext2fs_u32_list_iterate_begin(ext2_u32_list bb,
 309                                         ext2_u32_iterate *ret)
 310 {
 311         ext2_u32_iterate iter;
 312         errcode_t               retval;
 313
 314         EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 315
 316         retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_iterate), &iter);
 317         if (retval)
 318                 return retval;
 319
 320         iter->magic = EXT2_ET_MAGIC_BADBLOCKS_ITERATE;
 321         iter->bb = bb;
 322         iter->ptr = 0;
 323         *ret = iter;
 324         return 0;
 325 }
 326
 327 errcode_t ext2fs_badblocks_list_iterate_begin(ext2_badblocks_list bb,
 328                                               ext2_badblocks_iterate *ret)
 329 {
 330         return ext2fs_u32_list_iterate_begin((ext2_u32_list) bb,
 331                                               (ext2_u32_iterate *) ret);
 332 }
 333
 334
 335 int ext2fs_u32_list_iterate(ext2_u32_iterate iter, __u32 *blk)
 336 {
 337         ext2_u32_list   bb;
 338
 339         if (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE)
 340                 return 0;
 341
 342         bb = iter->bb;
 343
 344         if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST)
 345                 return 0;
 346
 347         if (iter->ptr < bb->num) {
 348                 *blk = bb->list[iter->ptr++];
 349                 return 1;
 350         }
 351         *blk = 0;
 352         return 0;
 353 }
 354
 355 int ext2fs_badblocks_list_iterate(ext2_badblocks_iterate iter, blk_t *blk)
 356 {
 357         return ext2fs_u32_list_iterate((ext2_u32_iterate) iter,
 358                                        (__u32 *) blk);
 359 }
 360
 361
 362 void ext2fs_u32_list_iterate_end(ext2_u32_iterate iter)
 363 {
 364         if (!iter || (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE))
 365                 return;
 366
 367         iter->bb = 0;
 368         ext2fs_free_mem(&iter);
 369 }
 370
 371 void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter)
 372 {
 373         ext2fs_u32_list_iterate_end((ext2_u32_iterate) iter);
 374 }
 375
 376
 377 int ext2fs_u32_list_equal(ext2_u32_list bb1, ext2_u32_list bb2)
 378 {
 379         EXT2_CHECK_MAGIC(bb1, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 380         EXT2_CHECK_MAGIC(bb2, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 381
 382         if (bb1->num != bb2->num)
 383                 return 0;
 384
 385         if (memcmp(bb1->list, bb2->list, bb1->num * sizeof(blk_t)) != 0)
 386                 return 0;
 387         return 1;
 388 }
 389
 390 int ext2fs_badblocks_equal(ext2_badblocks_list bb1, ext2_badblocks_list bb2)
 391 {
 392         return ext2fs_u32_list_equal((ext2_u32_list) bb1,
 393                                      (ext2_u32_list) bb2);
 394 }
 395
 396 int ext2fs_u32_list_count(ext2_u32_list bb)
 397 {
 398         return bb->num;
 399 }