src/bin/bfs_tools/lib/Bitmap.cpp

   1 /*
   2  * Copyright 2001-2008, pinc Software. All Rights Reserved.
   3  */
   4
   5 //!     handles the BFS block bitmap
   6
   7
   8 #include "Bitmap.h"
   9 #include "Disk.h"
  10 #include "Inode.h"
  11
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15
  16
  17 Bitmap::Bitmap(Disk *disk)
  18         :
  19         fBitmap(NULL),
  20         fBackupBitmap(NULL)
  21 {
  22         SetTo(disk);
  23 }
  24
  25
  26 Bitmap::Bitmap()
  27         :
  28         fDisk(NULL),
  29         fBitmap(NULL),
  30         fBackupBitmap(NULL),
  31         fSize(0L),
  32         fByteSize(0L),
  33         fUsedBlocks(0LL)
  34 {
  35 }
  36
  37
  38 Bitmap::~Bitmap()
  39 {
  40         free(fBitmap);
  41         free(fBackupBitmap);
  42 }
  43
  44
  45 status_t
  46 Bitmap::SetTo(Disk *disk)
  47 {
  48         free(fBitmap);
  49
  50         fDisk = disk;
  51         fSize = divide_roundup(disk->NumBlocks(),disk->BlockSize() * 8);
  52         fByteSize = disk->BlockSize() * disk->SuperBlock()->num_ags
  53                 * disk->SuperBlock()->blocks_per_ag;
  54
  55         fBitmap = (uint32 *)malloc(fByteSize);
  56         if (!fBitmap)
  57                 return B_NO_MEMORY;
  58
  59         fBackupBitmap = (uint32 *)malloc(fByteSize);
  60         if (fBackupBitmap == NULL)
  61                 return B_NO_MEMORY;
  62
  63         memset(fBackupBitmap, 0, fByteSize);
  64
  65         // set root block, block bitmap, log as used
  66         off_t end = disk->ToBlock(disk->Log()) + disk->Log().length;
  67         for (off_t block = 0; block < end; block++) {
  68                 if (!BackupSetAt(block, true))
  69                         break;
  70         }
  71
  72         ssize_t size;
  73         if ((size = disk->ReadAt(disk->BlockSize(), fBitmap, fByteSize)) < B_OK) {
  74                 free(fBitmap);
  75                 fBitmap = NULL;
  76
  77                 free(fBackupBitmap);
  78                 fBackupBitmap = NULL;
  79                 return size;
  80         }
  81
  82         // calculate used blocks
  83
  84         fUsedBlocks = 0LL;
  85         for (uint32 i = fByteSize >> 2;i-- > 0;) {
  86                 uint32 compare = 1;
  87                 for (int16 j = 0;j < 32;j++,compare <<= 1) {
  88                         if (compare & fBitmap[i])
  89                                 fUsedBlocks++;
  90                 }
  91         }
  92
  93         return B_OK;
  94 }
  95
  96
  97 status_t
  98 Bitmap::InitCheck()
  99 {
 100         return fBitmap ? B_OK : B_ERROR;
 101 }
 102
 103
 104 off_t
 105 Bitmap::FreeBlocks() const
 106 {
 107         if (fDisk == NULL)
 108                 return 0;
 109
 110         return fDisk->NumBlocks() - fUsedBlocks;
 111 }
 112
 113
 114 bool
 115 Bitmap::UsedAt(off_t block) const
 116 {
 117         uint32 index = block / 32;      // 32bit resolution, (beginning with block 1?)
 118         if (index > fByteSize / 4)
 119                 return false;
 120
 121         return fBitmap[index] & (1L << (block & 0x1f));
 122 }
 123
 124
 125 bool
 126 Bitmap::BackupUsedAt(off_t block) const
 127 {
 128         uint32 index = block / 32;      // 32bit resolution, (beginning with block 1?)
 129         if (index > fByteSize / 4)
 130                 return false;
 131
 132         return fBackupBitmap[index] & (1L << (block & 0x1f));
 133 }
 134
 135
 136 bool
 137 Bitmap::BackupSetAt(off_t block, bool used)
 138 {
 139         uint32 index = block / 32;
 140         if (index > fByteSize / 4) {
 141                 fprintf(stderr, "Bitmap::BackupSetAt(): Block %" B_PRIdOFF " outside "
 142                         "bitmap!\n", block);
 143                 return false;
 144         }
 145
 146         int32 mask = 1L << (block & 0x1f);
 147
 148         bool oldUsed = fBackupBitmap[index] & mask;
 149
 150         if (used)
 151                 fBackupBitmap[index] |= mask;
 152         else
 153                 fBackupBitmap[index] &= ~mask;
 154
 155         return oldUsed;
 156 }
 157
 158
 159 void
 160 Bitmap::BackupSet(Inode *inode, bool used)
 161 {
 162         // set inode and its data-stream
 163
 164         // the attributes are ignored for now, because they will
 165         // be added anyway since all inodes from disk are collected.
 166
 167 //      printf("a: %Ld\n",inode->Block());
 168         BackupSetAt(inode->Block(),used);
 169
 170         // the data stream of symlinks is no real data stream
 171         if (inode->IsSymlink() && (inode->Flags() & INODE_LONG_SYMLINK) == 0)
 172                 return;
 173
 174         // direct blocks
 175
 176         const bfs_inode *node = inode->InodeBuffer();
 177         for (int32 i = 0; i < NUM_DIRECT_BLOCKS; i++) {
 178                 if (node->data.direct[i].IsZero())
 179                         break;
 180
 181                 off_t start = fDisk->ToBlock(node->data.direct[i]);
 182                 off_t end = start + node->data.direct[i].length;
 183                 for (off_t block = start; block < end; block++) {
 184                         if (!BackupSetAt(block, used)) {
 185                                 //dump_inode(node);
 186                                 break;
 187                         }
 188                 }
 189         }
 190
 191         // indirect blocks
 192
 193         if (node->data.max_indirect_range == 0 || node->data.indirect.IsZero())
 194                 return;
 195
 196 //      printf("c: %Ld\n",fDisk->ToBlock(node->data.indirect));
 197         BackupSetAt(fDisk->ToBlock(node->data.indirect), used);
 198
 199         DataStream *stream = dynamic_cast<DataStream *>(inode);
 200         if (stream == NULL)
 201                 return;
 202
 203         // load indirect blocks
 204         int32 bytes = node->data.indirect.length << fDisk->BlockShift();
 205         block_run *indirect = (block_run *)malloc(bytes);
 206         if (indirect == NULL)
 207                 return;
 208
 209         if (fDisk->ReadAt(fDisk->ToOffset(node->data.indirect), indirect,
 210                         bytes) <= 0)
 211                 return;
 212
 213         int32 runs = bytes / sizeof(block_run);
 214         for (int32 i = 0; i < runs; i++) {
 215                 if (indirect[i].IsZero())
 216                         break;
 217
 218                 off_t start = fDisk->ToBlock(indirect[i]);
 219                 off_t end = start + indirect[i].length;
 220                 for (off_t block = start; block < end; block++) {
 221 //                      printf("d: %Ld\n", block);
 222                         if (!BackupSetAt(block, used))
 223                                 break;
 224                 }
 225         }
 226         free(indirect);
 227
 228         // double indirect blocks
 229
 230         if (node->data.max_double_indirect_range == 0
 231                 || node->data.double_indirect.IsZero())
 232                 return;
 233
 234 //      printf("e: %Ld\n",fDisk->ToBlock(node->data.double_indirect));
 235         BackupSetAt(fDisk->ToBlock(node->data.double_indirect), used);
 236
 237         // FIXME: to be implemented...
 238         puts("double indirect blocks to block bitmap requested...");
 239 }
 240
 241
 242 status_t
 243 Bitmap::Validate()
 244 {
 245         return B_OK;
 246 }
 247
 248
 249 status_t
 250 Bitmap::CompareWithBackup()
 251 {
 252         for (int32 i = fByteSize / 4;i-- > 0;) {
 253                 if (fBitmap[i] != fBackupBitmap[i]) {
 254                         printf("differ at %" B_PRId32 " (block %" B_PRId32 ") -> bitmap = "
 255                                 "%08" B_PRIx32 ", backup = %08" B_PRIx32 "\n", i, i * 32,
 256                                 fBitmap[i], fBackupBitmap[i]);
 257                 }
 258         }
 259         return B_OK;
 260 }
 261
 262
 263 bool
 264 Bitmap::TrustBlockContaining(off_t /*block*/) const
 265 {
 266         return true;
 267 }
 268