src/bin/bfs_tools/lib/Bitmap.cpp

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