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: %lld\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: %lld\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: %lld\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: %lld\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 270