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 %Ld outside bitmap!\n", 142 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 %ld (block %ld) -> bitmap = %08lx, backup = %08lx\n",i,i*32,fBitmap[i],fBackupBitmap[i]); 255 } 256 } 257 return B_OK; 258 } 259 260 261 bool 262 Bitmap::TrustBlockContaining(off_t /*block*/) const 263 { 264 return true; 265 } 266 267