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_badblocks_list(int size, int num, blk_t *list,
  33                                      ext2_badblocks_list *ret)
  34 {
  35         ext2_badblocks_list     bb;
  36         errcode_t               retval;
  37
  38         retval = ext2fs_get_mem(sizeof(struct ext2_struct_badblocks_list),
  39                                 (void **) &bb);
  40         if (retval)
  41                 return retval;
  42         memset(bb, 0, sizeof(struct ext2_struct_badblocks_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), (void **) &bb->list);
  47         if (!bb->list) {
  48                 ext2fs_free_mem((void **) &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 badblocks list.
  62  */
  63 errcode_t ext2fs_badblocks_list_create(ext2_badblocks_list *ret, int size)
  64 {
  65         return make_badblocks_list(size, 0, 0, ret);
  66 }
  67
  68 /*
  69  * This procedure copies a badblocks list
  70  */
  71 errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
  72                                 ext2_badblocks_list *dest)
  73 {
  74         errcode_t       retval;
  75
  76         retval = make_badblocks_list(src->size, src->num, src->list,
  77                                      dest);
  78         if (retval)
  79                 return retval;
  80         (*dest)->badblocks_flags = src->badblocks_flags;
  81         return 0;
  82 }
  83
  84
  85 /*
  86  * This procedure frees a badblocks list.
  87  *
  88  * (note: moved to closefs.c)
  89  */
  90
  91
  92 /*
  93  * This procedure adds a block to a badblocks list.
  94  */
  95 errcode_t ext2fs_badblocks_list_add(ext2_badblocks_list bb, blk_t blk)
  96 {
  97         errcode_t       retval;
  98         int             i, j;
  99         unsigned long   old_size;
 100
 101         EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 102
 103         if (bb->num >= bb->size) {
 104                 old_size = bb->size * sizeof(blk_t);
 105                 bb->size += 100;
 106                 retval = ext2fs_resize_mem(old_size, bb->size * sizeof(blk_t),
 107                                            (void **) &bb->list);
 108                 if (retval) {
 109                         bb->size -= 100;
 110                         return retval;
 111                 }
 112         }
 113
 114         /*
 115          * Add special case code for appending to the end of the list
 116          */
 117         i = bb->num-1;
 118         if ((bb->num != 0) && (bb->list[i] == blk))
 119                 return 0;
 120         if ((bb->num == 0) || (bb->list[i] < blk)) {
 121                 bb->list[bb->num++] = blk;
 122                 return 0;
 123         }
 124
 125         j = bb->num;
 126         for (i=0; i < bb->num; i++) {
 127                 if (bb->list[i] == blk)
 128                         return 0;
 129                 if (bb->list[i] > blk) {
 130                         j = i;
 131                         break;
 132                 }
 133         }
 134         for (i=bb->num; i > j; i--)
 135                 bb->list[i] = bb->list[i-1];
 136         bb->list[j] = blk;
 137         bb->num++;
 138         return 0;
 139 }
 140
 141 /*
 142  * This procedure tests to see if a particular block is on a badblocks
 143  * list.
 144  */
 145 int ext2fs_badblocks_list_test(ext2_badblocks_list bb, blk_t blk)
 146 {
 147         int     low, high, mid;
 148
 149         if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST)
 150                 return 0;
 151
 152         if (bb->num == 0)
 153                 return 0;
 154
 155         low = 0;
 156         high = bb->num-1;
 157         if (blk == bb->list[low])
 158                 return 1;
 159         if (blk == bb->list[high])
 160                 return 1;
 161
 162         while (low < high) {
 163                 mid = (low+high)/2;
 164                 if (mid == low || mid == high)
 165                         break;
 166                 if (blk == bb->list[mid])
 167                         return 1;
 168                 if (blk < bb->list[mid])
 169                         high = mid;
 170                 else
 171                         low = mid;
 172         }
 173         return 0;
 174 }
 175
 176 errcode_t ext2fs_badblocks_list_iterate_begin(ext2_badblocks_list bb,
 177                                               ext2_badblocks_iterate *ret)
 178 {
 179         ext2_badblocks_iterate iter;
 180         errcode_t               retval;
 181
 182         EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 183
 184         retval = ext2fs_get_mem(sizeof(struct ext2_struct_badblocks_iterate),
 185                               (void **) &iter);
 186         if (retval)
 187                 return retval;
 188
 189         iter->magic = EXT2_ET_MAGIC_BADBLOCKS_ITERATE;
 190         iter->bb = bb;
 191         iter->ptr = 0;
 192         *ret = iter;
 193         return 0;
 194 }
 195
 196 int ext2fs_badblocks_list_iterate(ext2_badblocks_iterate iter, blk_t *blk)
 197 {
 198         ext2_badblocks_list     bb;
 199
 200         if (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE)
 201                 return 0;
 202
 203         bb = iter->bb;
 204
 205         if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST)
 206                 return 0;
 207
 208         if (iter->ptr < bb->num) {
 209                 *blk = bb->list[iter->ptr++];
 210                 return 1;
 211         }
 212         *blk = 0;
 213         return 0;
 214 }
 215
 216 void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter)
 217 {
 218         if (!iter || (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE))
 219                 return;
 220
 221         iter->bb = 0;
 222         ext2fs_free_mem((void **) &iter);
 223 }
 224
 225 int ext2fs_badblocks_equal(ext2_badblocks_list bb1, ext2_badblocks_list bb2)
 226 {
 227         EXT2_CHECK_MAGIC(bb1, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 228         EXT2_CHECK_MAGIC(bb2, EXT2_ET_MAGIC_BADBLOCKS_LIST);
 229
 230         if (bb1->num != bb2->num)
 231                 return 0;
 232
 233         if (memcmp(bb1->list, bb2->list, bb1->num * sizeof(blk_t)) != 0)
 234                 return 0;
 235         return 1;
 236 }