![]() |
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 /* 00030 * Buffer to store the number of clusters of each kind. 00031 * More details at http://www.thescripts.com/forum/thread617704.html 00032 * ('Dynamically-allocated Multi-dimensional Arrays - C'). 00033 */ 00034 ULONGLONG (*new_cluster_map)[NUM_OF_SPACE_STATES] = NULL; 00035 ULONG map_size = 0; 00036 00037 ULONGLONG clusters_per_cell = 0; 00038 ULONGLONG clusters_per_last_cell = 0; /* last block can represent more clusters */ 00039 BOOLEAN opposite_order = FALSE; /* if true then number of clusters is less than number of blocks */ 00040 ULONGLONG cells_per_cluster = 0; 00041 ULONGLONG cells_per_last_cluster = 0; 00042 00048 int AllocateMap(int size) 00049 { 00050 LARGE_INTEGER interval; 00051 NTSTATUS Status; 00052 int buffer_size; 00053 00054 /* synchronize with GetMap requests */ 00055 interval.QuadPart = (-1 * 10000 * 1000); /* 1 sec */ 00056 Status = NtWaitForSingleObject(hMapEvent,FALSE,&interval); 00057 if(Status == STATUS_TIMEOUT || !NT_SUCCESS(Status)){ 00058 DebugPrint("NtWaitForSingleObject(hMapEvent,...) failed: %x!", 00059 (UINT)Status); 00060 return (-1); 00061 } 00062 00063 DebugPrint("Map size = %u\n",size); 00064 if(new_cluster_map) FreeMap(); 00065 if(!size){ 00066 (void)NtSetEvent(hMapEvent,NULL); 00067 return 0; /* console/native apps may work without cluster map */ 00068 } 00069 buffer_size = NUM_OF_SPACE_STATES * size * sizeof(ULONGLONG); 00070 new_cluster_map = winx_heap_alloc(buffer_size); 00071 if(!new_cluster_map){ 00072 DebugPrint("Cannot allocate %u bytes of memory for cluster map!", 00073 buffer_size); 00074 out_of_memory_condition_counter ++; 00075 (void)NtSetEvent(hMapEvent,NULL); 00076 return (-1); 00077 } 00078 map_size = size; 00079 memset(new_cluster_map,0,buffer_size); 00080 /* reset specific variables */ 00081 clusters_per_cell = 0; 00082 clusters_per_last_cell = 0; 00083 opposite_order = FALSE; 00084 cells_per_cluster = 0; 00085 cells_per_last_cluster = 0; 00086 (void)NtSetEvent(hMapEvent,NULL); 00087 return 0; 00088 } 00089 00098 int GetMap(char *dest,int cluster_map_size) 00099 { 00100 LARGE_INTEGER interval; 00101 NTSTATUS Status; 00102 ULONG i, k, index; 00103 ULONGLONG maximum, n; 00104 00105 /* synchronize with map reallocation */ 00106 interval.QuadPart = (-1); /* 100 nsec */ 00107 Status = NtWaitForSingleObject(hMapEvent,FALSE,&interval); 00108 if(Status == STATUS_TIMEOUT || !NT_SUCCESS(Status)) return (-1); 00109 00110 /* copy data */ 00111 if(!new_cluster_map){ 00112 (void)NtSetEvent(hMapEvent,NULL); 00113 return (-1); 00114 } 00115 if(cluster_map_size != map_size){ 00116 DebugPrint("Map size is wrong: %u != %u!\n", 00117 cluster_map_size,map_size); 00118 (void)NtSetEvent(hMapEvent,NULL); 00119 return (-1); 00120 } 00121 for(i = 0; i < map_size; i++){ 00122 maximum = new_cluster_map[i][0]; 00123 index = 0; 00124 for(k = 1; k < NUM_OF_SPACE_STATES; k++){ 00125 n = new_cluster_map[i][k]; 00126 if(n >= maximum){ /* support of colors precedence */ 00127 maximum = n; 00128 index = k; 00129 } 00130 } 00131 dest[i] = (char)index; 00132 } 00133 (void)NtSetEvent(hMapEvent,NULL); 00134 return 0; 00135 } 00136 00142 void MarkAllSpaceAsFree0(void) 00143 { 00144 ULONG i; 00145 00146 if(!new_cluster_map) return; 00147 memset(new_cluster_map,0,NUM_OF_SPACE_STATES * map_size * sizeof(ULONGLONG)); 00148 for(i = 0; i < map_size; i++) 00149 new_cluster_map[i][FREE_SPACE] = 1; 00150 } 00151 00157 void MarkAllSpaceAsSystem1(void) 00158 { 00159 ULONG i; 00160 00161 if(!new_cluster_map) return; 00162 /* calculate map parameters */ 00163 clusters_per_cell = clusters_total / map_size; 00164 if(clusters_per_cell){ 00165 opposite_order = FALSE; 00166 clusters_per_last_cell = clusters_per_cell + \ 00167 (clusters_total - clusters_per_cell * map_size); 00168 for(i = 0; i < map_size - 1; i++) 00169 new_cluster_map[i][SYSTEM_SPACE] = clusters_per_cell; 00170 new_cluster_map[i][SYSTEM_SPACE] = clusters_per_last_cell; 00171 } else { 00172 opposite_order = TRUE; 00173 cells_per_cluster = map_size / clusters_total; 00174 cells_per_last_cluster = cells_per_cluster + \ 00175 (map_size - cells_per_cluster * clusters_total); 00176 DebugPrint("Opposite order %I64u:%I64u:%I64u\n", \ 00177 clusters_total,cells_per_cluster,cells_per_last_cluster); 00178 } 00179 } 00180 00187 unsigned char GetFileSpaceState(PFILENAME pfn) 00188 { 00189 UCHAR space_states[] = {UNFRAGM_SPACE,UNFRAGM_OVERLIMIT_SPACE, \ 00190 COMPRESSED_SPACE,COMPRESSED_OVERLIMIT_SPACE, \ 00191 DIR_SPACE,DIR_OVERLIMIT_SPACE,DIR_SPACE, \ 00192 DIR_OVERLIMIT_SPACE}; 00193 int d,c,o; 00194 unsigned char state; 00195 PBLOCKMAP block; 00196 int i; 00197 00198 /* show $MFT file in dark magenta color */ 00199 if(IsMft(pfn)){ 00200 i = 0; 00201 for(block = pfn->blockmap; block != NULL; block = block->next_ptr){ 00202 DebugPrint("MFT part #%u start: %I64u, length: %I64u\n", 00203 i,block->lcn,block->length); 00204 i ++; 00205 if(block->next_ptr == pfn->blockmap) break; 00206 } 00207 return MFT_SPACE; 00208 } 00209 00210 /* 00211 * Show filtered out stuff and files above size threshold 00212 * and reparse points as unfragmented. 00213 */ 00214 if(pfn->is_fragm && !pfn->is_filtered && !pfn->is_overlimit && !pfn->is_reparse_point) 00215 state = pfn->is_overlimit ? FRAGM_OVERLIMIT_SPACE : FRAGM_SPACE; 00216 else{ 00217 d = (int)(pfn->is_dir) & 0x1; 00218 c = (int)(pfn->is_compressed) & 0x1; 00219 o = (int)(pfn->is_overlimit) & 0x1; 00220 state = space_states[(d << 2) + (c << 1) + o]; 00221 } 00222 return state; 00223 } 00224 00228 static BOOLEAN IsOutsideMft(ULONGLONG start,ULONGLONG len) 00229 { 00230 if(mft_end == 0 || (start + len) <= mft_start || start > mft_end) return TRUE; 00231 return FALSE; 00232 } 00233 00237 static BOOLEAN IsOutsideMftZone(ULONGLONG start,ULONGLONG len) 00238 { 00239 if(mftzone_end == 0 || (start + len) <= mftzone_start || start > mftzone_end) return TRUE; 00240 return FALSE; 00241 } 00242 00246 static BOOLEAN IsOutsideMftMirr(ULONGLONG start,ULONGLONG len) 00247 { 00248 if(mftmirr_end == 0 || (start + len) <= mftmirr_start || start > mftmirr_end) return TRUE; 00249 return FALSE; 00250 } 00251 00255 static BOOLEAN IsInsideMft(ULONGLONG start,ULONGLONG len) 00256 { 00257 if(mft_end != 0 && start >= mft_start && (start + len) <= (mft_end + 1)) return TRUE; 00258 return FALSE; 00259 } 00260 00264 static BOOLEAN IsInsideMftZone(ULONGLONG start,ULONGLONG len) 00265 { 00266 if(mftzone_end != 0 && start >= mftzone_start && (start + len) <= (mftzone_end + 1)) return TRUE; 00267 return FALSE; 00268 } 00269 00273 static BOOLEAN IsInsideMftMirr(ULONGLONG start,ULONGLONG len) 00274 { 00275 if(mftmirr_end != 0 && start >= mftmirr_start && (start + len) <= (mftmirr_end + 1)) return TRUE; 00276 return FALSE; 00277 } 00278 00292 static void RemarkBlockRespectToMftZones(ULONGLONG start,ULONGLONG len, 00293 int new_space_state,int old_space_state, 00294 BOOLEAN adjust_new_space_state) 00295 { 00296 BOOLEAN outside_mft, outside_mftzone, outside_mftmirr; 00297 BOOLEAN inside_mft, inside_mftzone, inside_mftmirr; 00298 ULONGLONG i; 00299 int default_space_state,adjusted_space_state; 00300 00301 if(adjust_new_space_state) default_space_state = new_space_state; 00302 else default_space_state = old_space_state; 00303 00304 /* check whether the block is outside mft zones */ 00305 outside_mft = IsOutsideMft(start,len); 00306 outside_mftzone = IsOutsideMftZone(start,len); 00307 outside_mftmirr = IsOutsideMftMirr(start,len); 00308 if(outside_mft && outside_mftzone && outside_mftmirr){ 00309 if(adjust_new_space_state) 00310 RemarkBlock(start,len,default_space_state,old_space_state); 00311 else 00312 RemarkBlock(start,len,new_space_state,default_space_state); 00313 } else { 00314 /* check whether the block is completely inside mft zone */ 00315 inside_mft = IsInsideMft(start,len); 00316 inside_mftzone = IsInsideMftZone(start,len); 00317 inside_mftmirr = IsInsideMftMirr(start,len); 00318 if(inside_mft || inside_mftzone || inside_mftmirr){ 00319 if(adjust_new_space_state) 00320 RemarkBlock(start,len,MFT_ZONE_SPACE,old_space_state); 00321 else 00322 RemarkBlock(start,len,new_space_state,MFT_ZONE_SPACE); 00323 } else { 00324 /* block is partially inside mft zone */ 00325 /* this case is rare, it may encounter mo more than 6 times */ 00326 /* therefore we can handle it easy, without optimizing the code for speed */ 00327 for(i = start; i < start + len; i++){ 00328 if((i < mft_start || i > mft_end) && (i < mftzone_start || i > mftzone_end) && 00329 (i < mftmirr_start || i > mftmirr_end)) 00330 adjusted_space_state = default_space_state; 00331 else 00332 adjusted_space_state = MFT_ZONE_SPACE; 00333 if(adjust_new_space_state) 00334 RemarkBlock(i,1,adjusted_space_state,old_space_state); 00335 else 00336 RemarkBlock(i,1,new_space_state,adjusted_space_state); 00337 } 00338 } 00339 } 00340 } 00341 00347 void MarkFileSpace(PFILENAME pfn,int old_space_state) 00348 { 00349 PBLOCKMAP block; 00350 UCHAR new_space_state; 00351 00352 new_space_state = GetFileSpaceState(pfn); 00353 for(block = pfn->blockmap; block != NULL; block = block->next_ptr){ 00354 RemarkBlock(block->lcn,block->length,new_space_state,old_space_state); 00355 if(block->next_ptr == pfn->blockmap) break; 00356 } 00357 } 00358 00363 void RemarkFileSpaceAsSystem(PFILENAME pfn) 00364 { 00365 PBLOCKMAP block; 00366 UCHAR state, new_state; 00367 00368 state = GetFileSpaceState(pfn); 00369 new_state = pfn->is_overlimit ? SYSTEM_OVERLIMIT_SPACE : SYSTEM_SPACE; 00370 for(block = pfn->blockmap; block != NULL; block = block->next_ptr){ 00371 RemarkBlock(block->lcn,block->length,new_state,state); 00372 if(block->next_ptr == pfn->blockmap) break; 00373 } 00374 } 00375 00383 void RemarkBlock(ULONGLONG start,ULONGLONG len,int space_state,int old_space_state) 00384 { 00385 ULONGLONG cell, offset, n; 00386 ULONGLONG ncells, i, j; 00387 ULONGLONG *c; 00388 PFREEBLOCKMAP block; 00389 ULONGLONG current_cluster, clusters_to_process, length; 00390 00391 /* return if we don't need cluster map */ 00392 if(!new_cluster_map) return; 00393 00394 /* check parameters */ 00395 if(space_state < 0 || (space_state >= NUM_OF_SPACE_STATES && space_state != FREE_OR_MFT_ZONE_SPACE)) return; 00396 if(old_space_state < 0 || (old_space_state >= NUM_OF_SPACE_STATES && 00397 old_space_state != SYSTEM_OR_FREE_SPACE && old_space_state != SYSTEM_OR_MFT_ZONE_SPACE)) return; 00398 if(start + len > clusters_total) return; 00399 00400 if(old_space_state == SYSTEM_OR_FREE_SPACE){ 00401 current_cluster = start; 00402 clusters_to_process = len; 00403 for(block = free_space_map; block != NULL; block = block->next_ptr){ 00404 /* break if current block follows the target */ 00405 if(block->lcn >= start + len){ 00406 if(clusters_to_process) 00407 RemarkBlock(current_cluster,clusters_to_process,space_state,SYSTEM_SPACE); 00408 break; 00409 } 00410 /* skip preceding blocks */ 00411 if(block->lcn >= current_cluster){ 00412 if(block->lcn > current_cluster){ 00413 length = block->lcn - current_cluster; 00414 RemarkBlock(current_cluster,length,space_state,SYSTEM_SPACE); 00415 current_cluster += length; 00416 clusters_to_process -= length; 00417 } 00418 /* now block->lcn is equal to current_block always */ 00419 length = min(block->length,clusters_to_process); 00420 RemarkBlock(current_cluster,length,space_state,FREE_SPACE); 00421 current_cluster += length; 00422 clusters_to_process -= length; 00423 } 00424 if(block->next_ptr == free_space_map) break; 00425 } 00426 return; 00427 } 00428 00429 if(old_space_state == SYSTEM_OR_MFT_ZONE_SPACE){ 00430 RemarkBlockRespectToMftZones(start,len,space_state,SYSTEM_SPACE,FALSE); 00431 return; 00432 } 00433 00434 if(space_state == FREE_OR_MFT_ZONE_SPACE){ 00435 RemarkBlockRespectToMftZones(start,len,FREE_SPACE,old_space_state,TRUE); 00436 return; 00437 } 00438 00439 if(!opposite_order){ 00440 if(!clusters_per_cell) return; 00441 /* 00442 * The following code uses _aulldvrm() function: 00443 * cell = start / dx->clusters_per_cell; 00444 * offset = start % dx->clusters_per_cell; 00445 * But we don't have this function on NT 4.0!!! 00446 */ 00447 cell = start / clusters_per_cell; 00448 offset = start - cell * clusters_per_cell; 00449 while((cell < (map_size - 1)) && len){ 00450 n = min(len,clusters_per_cell - offset); 00451 new_cluster_map[cell][space_state] += n; 00452 c = &new_cluster_map[cell][old_space_state]; 00453 if(*c >= n) *c -= n; else *c = 0; 00454 len -= n; 00455 cell ++; 00456 offset = 0; 00457 } 00458 00459 /* ckeck cell correctness */ 00460 if(cell >= map_size) return; /* important !!! */ 00461 00462 if(len){ 00463 n = min(len,clusters_per_last_cell - offset); 00464 new_cluster_map[cell][space_state] += n; 00465 c = &new_cluster_map[cell][old_space_state]; 00466 if(*c >= n) *c -= n; else *c = 0; 00467 } 00468 } else { /* dx->opposite_order */ 00469 cell = start * cells_per_cluster; 00470 ncells = len * cells_per_cluster; 00471 /*if(start + len > dx->clusters_total) KeBugCheck();*/ 00472 if(start + len == clusters_total) 00473 ncells += (cells_per_last_cluster - cells_per_cluster); 00474 for(i = 0; i < ncells; i++){ 00475 for(j = 0; j < NUM_OF_SPACE_STATES; j++) 00476 new_cluster_map[cell + i][j] = 0; 00477 new_cluster_map[cell + i][space_state] = 1; 00478 } 00479 } 00480 } 00481 00485 void FreeMap(void) 00486 { 00487 if(new_cluster_map){ 00488 winx_heap_free(new_cluster_map); 00489 new_cluster_map = NULL; 00490 } 00491 map_size = 0; 00492 } 00493