![]() |
UltraDefrag Engine Architecture - Reference Manual - Guides |
|
00001 /* 00002 * UltraDefrag - powerful defragmentation tool for Windows NT. 00003 * Copyright (c) 2007-2010 by Dmitri Arkhangelski (dmitriar@gmail.com). 00004 * 00005 * This program is free software; you can redistribute it and/or modify 00006 * it under the terms of the GNU General Public License as published by 00007 * the Free Software Foundation; either version 2 of the License, or 00008 * (at your option) any later version. 00009 * 00010 * This program is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 * GNU General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU General Public License 00016 * along with this program; if not, write to the Free Software 00017 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 00027 #include "globals.h" 00028 00029 static FREEBLOCKMAP *AddLastFreeBlock(ULONGLONG start,ULONGLONG length); 00030 00037 NTSTATUS FillFreeSpaceMap(void) 00038 { 00039 char *BitMap; 00040 NTSTATUS status; 00041 PBITMAP_DESCRIPTOR bitMappings; 00042 ULONGLONG cluster,startLcn; 00043 IO_STATUS_BLOCK ioStatus; 00044 ULONGLONG i; 00045 ULONGLONG len; 00046 /* Bit shifting array for efficient processing of the bitmap */ 00047 UCHAR BitShift[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 00048 ULONGLONG nextLcn; 00049 00050 /* allocate memory */ 00051 BitMap = winx_heap_alloc(BITMAPSIZE * sizeof(UCHAR)); 00052 if(BitMap == NULL){ 00053 DebugPrint("Cannot allocate memory for FillFreeSpaceMap()!\n"); 00054 out_of_memory_condition_counter ++; 00055 return STATUS_NO_MEMORY; 00056 } 00057 00058 /* start scanning */ 00059 bitMappings = (PBITMAP_DESCRIPTOR)BitMap; 00060 nextLcn = 0; cluster = LLINVALID; 00061 do { 00062 RtlZeroMemory(bitMappings,BITMAPSIZE); 00063 status = NtFsControlFile(winx_fileno(fVolume),NULL,NULL,0,&ioStatus, 00064 FSCTL_GET_VOLUME_BITMAP,&nextLcn,sizeof(cluster),bitMappings,BITMAPSIZE); 00065 if(NT_SUCCESS(status)/* == STATUS_PENDING*/){ 00066 NtWaitForSingleObject(winx_fileno(fVolume),FALSE,NULL); 00067 status = ioStatus.Status; 00068 } 00069 if(status != STATUS_SUCCESS && status != STATUS_BUFFER_OVERFLOW){ 00070 DebugPrint("Get Volume Bitmap Error: %x!\n",(UINT)status); 00071 winx_heap_free(BitMap); 00072 return status; 00073 } 00074 /* Scan through the returned bitmap info. */ 00075 startLcn = bitMappings->StartLcn; 00076 for(i = 0; i < min(bitMappings->ClustersToEndOfVol,8*BITMAPBYTES); i++){ 00077 if(!(bitMappings->Map[ i/8 ] & BitShift[ i % 8 ])){ 00078 /* Cluster is free */ 00079 if(cluster == LLINVALID) 00080 cluster = startLcn + i; 00081 } else { 00082 /* Cluster isn't free */ 00083 if(cluster != LLINVALID){ 00084 len = startLcn + i - cluster; 00085 DebugPrint2("start: %I64u len: %I64u\n",cluster,len); 00086 if(!AddLastFreeBlock(cluster,len)){ 00087 winx_heap_free(BitMap); 00088 return STATUS_NO_MEMORY; 00089 } 00090 Stat.processed_clusters += len; 00091 cluster = LLINVALID; 00092 } 00093 } 00094 } 00095 /* Move to the next block */ 00096 nextLcn = bitMappings->StartLcn + i; 00097 } while(status != STATUS_SUCCESS); 00098 00099 if(cluster != LLINVALID){ 00100 len = startLcn + i - cluster; 00101 DebugPrint2("start: %I64u len: %I64u\n",cluster,len); 00102 if(!AddLastFreeBlock(cluster,len)){ 00103 winx_heap_free(BitMap); 00104 return STATUS_NO_MEMORY; 00105 } 00106 Stat.processed_clusters += len; 00107 } 00108 winx_heap_free(BitMap); 00109 return STATUS_SUCCESS; 00110 } 00111 00125 void ProcessFreedBlock(ULONGLONG start,ULONGLONG len,UCHAR old_space_state) 00126 { 00127 /* 00128 * On FAT partitions after file moving filesystem driver marks 00129 * previously allocated clusters as free immediately. 00130 * But on NTFS they are always allocated by system, not free, never free. 00131 * Only the next volume analysis frees them. 00132 */ 00133 if(partition_type == NTFS_PARTITION){ 00134 /* mark clusters as temporarily allocated by system */ 00135 RemarkBlock(start,len,TEMPORARY_SYSTEM_SPACE,old_space_state); 00136 } else { 00137 RemarkBlock(start,len,FREE_SPACE,old_space_state); 00138 AddFreeSpaceBlock(start,len); 00139 } 00140 } 00141 00147 void AddFreeSpaceBlock(ULONGLONG start,ULONGLONG length) 00148 { 00149 PFREEBLOCKMAP block, prev_block = NULL, next_block; 00150 00151 for(block = free_space_map; block != NULL; block = block->next_ptr){ 00152 if(block->lcn > start){ 00153 if(block != free_space_map) prev_block = block->prev_ptr; 00154 break; 00155 } 00156 if(block->next_ptr == free_space_map){ 00157 prev_block = block; 00158 break; 00159 } 00160 } 00161 00162 /* hits the new block previous? */ 00163 if(prev_block){ 00164 if(prev_block->lcn + prev_block->length == start){ 00165 prev_block->length += length; 00166 if(prev_block->lcn + prev_block->length == prev_block->next_ptr->lcn){ 00167 prev_block->length += prev_block->next_ptr->length; 00168 prev_block->next_ptr->length = 0; 00169 } 00170 return; 00171 } 00172 } 00173 00174 /* hits the new block the next one? */ 00175 if(free_space_map){ 00176 if(prev_block == NULL) next_block = free_space_map; 00177 else next_block = prev_block->next_ptr; 00178 if(start + length == next_block->lcn){ 00179 next_block->lcn = start; 00180 next_block->length += length; 00181 return; 00182 } 00183 } 00184 00185 block = (PFREEBLOCKMAP)winx_list_insert_item((list_entry **)(void *)&free_space_map, 00186 (list_entry *)prev_block,sizeof(FREEBLOCKMAP)); 00187 if(!block) return; 00188 00189 block->lcn = start; 00190 block->length = length; 00191 } 00192 00200 static FREEBLOCKMAP *AddLastFreeBlock(ULONGLONG start,ULONGLONG length) 00201 { 00202 PFREEBLOCKMAP block, lastblock = NULL; 00203 00204 if(free_space_map) lastblock = free_space_map->prev_ptr; 00205 block = (PFREEBLOCKMAP)winx_list_insert_item((list_entry **)(void *)&free_space_map, 00206 (list_entry *)lastblock,sizeof(FREEBLOCKMAP)); 00207 if(block){ 00208 block->lcn = start; 00209 block->length = length; 00210 } 00211 00212 /* mark space */ 00213 RemarkBlock(start,length,FREE_SPACE,SYSTEM_SPACE); 00214 return block; 00215 } 00216 00225 void TruncateFreeSpaceBlock(ULONGLONG start,ULONGLONG length) 00226 { 00227 PFREEBLOCKMAP block; 00228 ULONGLONG n; 00229 00230 for(block = free_space_map; block != NULL; block = block->next_ptr){ 00231 if(block->lcn == start){ 00232 n = min(block->length,length); 00233 block->lcn += n; 00234 block->length -= n; 00235 return; 00236 } 00237 if(block->next_ptr == free_space_map) break; 00238 } 00239 DebugPrint("TruncateFreeSpaceBlock() failed: Lcn=%I64u!\n",start); 00240 } 00241 00247 void RemoveFreeSpaceBlock(ULONGLONG start,ULONGLONG len) 00248 { 00249 PFREEBLOCKMAP block; 00250 ULONGLONG new_lcn, new_length; 00251 00252 for(block = free_space_map; block != NULL; block = block->next_ptr){ 00253 if(block->lcn >= start && (block->lcn + block->length) <= (start + len)){ 00254 /* 00255 * block is inside a specified range 00256 * |--------------------| 00257 * |block| 00258 */ 00259 block->length = 0; 00260 goto next_block; 00261 } 00262 if(block->lcn < start && (block->lcn + block->length) > start && \ 00263 (block->lcn + block->length) <= (start + len)){ 00264 /* 00265 * cut the right side of block 00266 * |--------------------| 00267 * |block| 00268 */ 00269 block->length = start - block->lcn; 00270 goto next_block; 00271 } 00272 if(block->lcn >= start && block->lcn < (start + len)){ 00273 /* 00274 * cut the left side of block 00275 * |--------------------| 00276 * |block| 00277 */ 00278 block->length = block->lcn + block->length - (start + len); 00279 block->lcn = start + len; 00280 goto next_block; 00281 } 00282 if(block->lcn < start && (block->lcn + block->length) > (start + len)){ 00283 /* 00284 * specified range is inside a block 00285 * |----| 00286 * |-------block--------| 00287 */ 00288 new_lcn = start + len; 00289 new_length = block->lcn + block->length - (start + len); 00290 block->length = start - block->lcn; 00291 AddFreeSpaceBlock(new_lcn,new_length); 00292 goto next_block; 00293 } 00294 00295 next_block: 00296 if(block->next_ptr == free_space_map) break; 00297 } 00298 } 00299 00303 void DbgPrintFreeSpaceList(void) 00304 { 00305 PFREEBLOCKMAP block; 00306 00307 for(block = free_space_map; block != NULL; block = block->next_ptr){ 00308 DebugPrint2("Free Block start: %I64u len: %I64u\n",block->lcn,block->length); 00309 if(block->next_ptr == free_space_map) break; 00310 } 00311 } 00312