defrag.c
1 /*
2  * UltraDefrag - a powerful defragmentation tool for Windows NT.
3  * Copyright (c) 2007-2018 Dmitri Arkhangelski (dmitriar@gmail.com).
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18  */
19 
28 /*
29 * Ideas by Stefan Pendl <stefanpe@users.sourceforge.net>
30 * and Dmitri Arkhangelski <dmitriar@gmail.com>.
31 */
32 
33 #include "udefrag-internals.h"
34 
35 static ULONGLONG defrag_cc_routine(udefrag_job_parameters *jp);
36 
37 /************************************************************/
38 /* Test suite */
39 /************************************************************/
40 
41 /*
42 * Uncomment it to test defragmentation
43 * of various special files like reparse
44 * points, attribute lists and others.
45 */
46 //#define TEST_SPECIAL_FILES_DEFRAG
47 
48 /* Test suite for special files. */
49 #ifdef TEST_SPECIAL_FILES_DEFRAG
50 void test_move(winx_file_info *f,udefrag_job_parameters *jp)
51 {
52  winx_volume_region *target_rgn;
53  ULONGLONG source_lcn = f->disp.blockmap->lcn;
54 
55  /* try to move the first cluster to the last free region */
56  target_rgn = find_last_free_region(jp,1);
57  if(target_rgn == NULL){
58  etrace("no free region found on disk");
59  return;
60  }
61  if(move_file(f,f->disp.blockmap->vcn,1,target_rgn->lcn,jp) < 0){
62  etrace("move failed for %ws",f->path);
63  return;
64  } else {
65  dtrace("move succeeded for %ws",f->path);
66  }
67  /* try to move the first cluster back */
68  if(can_move(f,jp)){
69  if(move_file(f,f->disp.blockmap->vcn,1,source_lcn,jp) < 0){
70  etrace("move failed for %ws",f->path);
71  return;
72  } else {
73  dtrace("move succeeded for %ws",f->path);
74  }
75  } else {
76  etrace("file became unmovable %ws",f->path);
77  }
78  /* release temporarily allocated space */
79  release_temp_space_regions(jp);
80 }
81 
82 /*
83 * Tests defragmentation of reparse points,
84 * encrypted files, bitmaps and attribute lists.
85 */
86 void test_special_files_defrag(udefrag_job_parameters *jp)
87 {
88  winx_file_info *f;
89  int special_file = 0;
90 
91  dtrace("test of special files defragmentation started");
92 
93  for(f = jp->filelist; f; f = f->next){
94  if(can_move(f,jp)){
95  special_file = 0;
96  if(is_reparse_point(f)){
97  dtrace("reparse point detected: %ws",f->path);
98  special_file = 1;
99  } else if(is_encrypted(f)){
100  dtrace("encrypted file detected: %ws",f->path);
101  special_file = 1;
102  } else if(winx_wcsistr(f->path,L"$BITMAP")){
103  dtrace("bitmap detected: %ws",f->path);
104  special_file = 1;
105  } else if(winx_wcsistr(f->path,L"$ATTRIBUTE_LIST")){
106  dtrace("attribute list detected: %ws",f->path);
107  special_file = 1;
108  }
109  if(special_file)
110  test_move(f,jp);
111  }
112  if(f->next == jp->filelist) break;
113  }
114 
115  dtrace("test of special files defragmentation completed");
116 }
117 #endif /* TEST_SPECIAL_FILES_DEFRAG */
118 
119 /************************************************************/
120 /* Auxiliary routines */
121 /************************************************************/
122 
127 static int can_defragment(winx_file_info *f,udefrag_job_parameters *jp)
128 {
129  if(!can_move(f,jp))
130  return 0;
131 
132  /* skip not fragmented files */
133  if(!is_fragmented(f))
134  return 0;
135 
136  /* skip MFT */
137  if(is_mft(f,jp))
138  return 0;
139 
140  /* skip FAT directories */
141  if(jp->is_fat && is_directory(f))
142  return 0;
143 
144  /* in MFT optimization defragment marked files only */
145  if(jp->job_type == MFT_OPTIMIZATION_JOB \
146  && !is_fragmented_by_file_opt(f))
147  return 0;
148 
149  return 1;
150 }
151 
156 static winx_blockmap *add_fragment(winx_blockmap **fragments,
157  winx_blockmap **prev_fragment, ULONGLONG vcn, ULONGLONG lcn,
158  ULONGLONG length)
159 {
160  winx_blockmap *fragment;
161 
162  fragment = (winx_blockmap *)winx_list_insert((list_entry **)(void *)fragments,
163  (list_entry *)*prev_fragment,sizeof(winx_blockmap));
164  fragment->vcn = vcn;
165  fragment->lcn = lcn;
166  fragment->length = length;
167  *prev_fragment = fragment;
168  return fragment;
169 }
170 
175 winx_blockmap *build_fragments_list(winx_file_info *f,ULONGLONG *n_fragments)
176 {
177  winx_blockmap *block, *p = NULL, *fragments = NULL;
178  ULONGLONG vcn = 0, lcn = 0, length = 0;
179 
180  if(n_fragments) *n_fragments = 0;
181 
182  for(block = f->disp.blockmap; block; block = block->next){
183  if(block == f->disp.blockmap){
184  vcn = block->vcn;
185  lcn = block->lcn;
186  length = block->length;
187  } else {
188  if(block->lcn == block->prev->lcn + block->prev->length){
189  length += block->length;
190  } else {
191  if(length){
192  if(!add_fragment(&fragments,&p,vcn,lcn,length))
193  break;
194  if(n_fragments) (*n_fragments) ++;
195  }
196  vcn = block->vcn;
197  lcn = block->lcn;
198  length = block->length;
199  }
200  }
201  if(block->next == f->disp.blockmap) break;
202  }
203 
204  if(length){
205  if(add_fragment(&fragments,&p,vcn,lcn,length)){
206  if(n_fragments) (*n_fragments) ++;
207  }
208  }
209 
210  if(fragments == NULL && n_fragments) *n_fragments = 0;
211  return fragments;
212 }
213 
218 void release_fragments_list(winx_blockmap **fragments)
219 {
220  winx_list_destroy((list_entry **)(void *)fragments);
221 }
222 
227 void clear_currently_excluded_flag(udefrag_job_parameters *jp)
228 {
229  winx_file_info *f;
230 
231  for(f = jp->filelist; f; f = f->next){
232  f->user_defined_flags &= ~UD_FILE_CURRENTLY_EXCLUDED;
233  if(f->next == jp->filelist) break;
234  }
235 }
236 
242 static ULONGLONG defrag_cc_routine(udefrag_job_parameters *jp)
243 {
244  struct prb_traverser t;
245  winx_file_info *file;
246  ULONGLONG n = 0;
247 
248  /* fine calculation will take too much time */
249  prb_t_init(&t,jp->fragmented_files);
250  file = prb_t_first(&t,jp->fragmented_files);
251  while(file){
252  if(jp->termination_router((void *)jp)) break;
253  /* count all fragmented files which can be processed */
254  if(can_defragment(file,jp)) n += file->disp.clusters;
255  file = prb_t_next(&t);
256  }
257  return n;
258 }
259 
265 static void defrag_routine(udefrag_job_parameters *jp)
266 {
267  winx_volume_region *rgn, *largest_rgn;
268  struct prb_traverser t;
269  winx_file_info *file, *next_file;
270  int move_entirely;
271  ULONGLONG defragmented_files;
272  ULONGLONG defragmented_entirely = 0, defragmented_partially = 0;
273  ULONGLONG x, moved_entirely = 0, moved_partially = 0;
274  ULONGLONG min_vcn, max_vcn; /* used to avoid infinite loops */
275  winx_blockmap *fragments, *fr, *fr2, *next_fr, *head_fr;
276  ULONGLONG vcn, length, n, new_min_vcn;
277  ULONGLONG cut_length;
278  int defrag_succeeded;
279  char buffer[32];
280 
281  winx_dbg_print_header(0,0,I"defragmentation pass #%u",++jp->pi.pass_number);
282  jp->pi.current_operation = VOLUME_DEFRAGMENTATION;
283  jp->pi.moved_clusters = 0;
284 
285  /* release temporarily allocated space */
286  release_temp_space_regions(jp);
287 
288  /* no files are excluded by this task currently */
289  clear_currently_excluded_flag(jp);
290 
291  jp->pi.clusters_to_process = \
292  jp->pi.processed_clusters + defrag_cc_routine(jp);
293 
294  /*
295  dtrace(">>> %I64u\\%I64u <<<",
296  jp->pi.processed_clusters,jp->pi.clusters_to_process);
297  */
298 
299  /*
300  * Eliminate little fragments. Defragment
301  * the most fragmented files first of all.
302  */
303  defragmented_files = 0;
304  prb_t_init(&t,jp->fragmented_files);
305  file = prb_t_first(&t,jp->fragmented_files);
306  while(file){
307  if(jp->termination_router((void *)jp)) break;
308  next_file = prb_t_next(&t);
309  if(can_defragment(file,jp)){
310  move_entirely = 0;
311  if(file->disp.clusters * jp->v_info.bytes_per_cluster \
312  < 2 * jp->udo.fragment_size_threshold) move_entirely = 1;
313  else if(jp->win_version < WINDOWS_XP && jp->fs_type == FS_NTFS)
314  move_entirely = 1; /* keep algorithm simple */
315  if(move_entirely){
316  /* move the entire file */
317  rgn = find_first_free_region(jp,0,file->disp.clusters,NULL);
318  if(rgn){
319  x = jp->pi.moved_clusters;
320  if(move_file(file,file->disp.blockmap->vcn,
321  file->disp.clusters,rgn->lcn,jp) >= 0){
322  if(jp->udo.dbgprint_level >= DBG_DETAILED)
323  itrace("Defrag success for %ws",file->path);
324  defragmented_files ++;
325  defragmented_entirely ++;
326  moved_entirely += (jp->pi.moved_clusters - x);
327  } else {
328  etrace("Defrag failure for %ws",file->path);
329  }
330  }
331  } else {
332  /* eliminate little fragments */
333  min_vcn = file->disp.blockmap->vcn;
334  max_vcn = file->disp.blockmap->prev->vcn + \
335  file->disp.blockmap->prev->length;
336  defrag_succeeded = 0;
337  x = jp->pi.moved_clusters;
338  while(min_vcn < max_vcn && can_defragment(file,jp)){
339  /* build list of fragments */
340  fragments = build_fragments_list(file,NULL);
341  if(fragments == NULL) break;
342 
343  /* cut off already processed fragments and data after max_vcn */
344  for(fr = fragments; fr; fr = next_fr){
345  head_fr = fragments;
346  next_fr = fr->next;
347  if(fr->vcn < min_vcn || (fr->vcn + fr->length > max_vcn))
348  winx_list_remove((list_entry **)(void *)&fragments,(list_entry *)(void *)fr);
349  if(fragments == NULL) goto completed;
350  if(next_fr == head_fr) break;
351  }
352 
353  /* how much clusters can we join together? */
354  largest_rgn = find_largest_free_region(jp);
355  if(largest_rgn == NULL) break;
356 
357  /* find clusters needing optimization */
358  vcn = length = n = new_min_vcn = 0;
359  for(fr = fragments; fr; fr = fr->next){
360  /* find the first little fragment */
361  if(fr->length * jp->v_info.bytes_per_cluster < jp->udo.fragment_size_threshold){
362  if(fr->length >= largest_rgn->length) break;
363  vcn = fr->vcn;
364  length = fr->length, n++;
365  new_min_vcn = fr->vcn + fr->length;
366  /* look forward for the next little fragments */
367  for(fr2 = fr->next; fr2 != fragments; fr2 = fr2->next){
368  if(fr2->length * jp->v_info.bytes_per_cluster >= jp->udo.fragment_size_threshold)
369  break;
370  if(length + fr2->length > largest_rgn->length) goto move_clusters;
371  length += fr2->length, n++;
372  new_min_vcn = fr2->vcn + fr2->length;
373  }
374  if(largest_rgn->length * jp->v_info.bytes_per_cluster < jp->udo.fragment_size_threshold) break;
375  if(length * jp->v_info.bytes_per_cluster < jp->udo.fragment_size_threshold){
376  cut_length = jp->udo.fragment_size_threshold / jp->v_info.bytes_per_cluster;
377  if(cut_length * jp->v_info.bytes_per_cluster != jp->udo.fragment_size_threshold)
378  cut_length ++;
379  cut_length -= length;
380  if(fr2 != fragments){
381  /* let's cut from the next fragment */
382  if((fr2->length - cut_length) * jp->v_info.bytes_per_cluster \
383  < jp->udo.fragment_size_threshold){
384  length += fr2->length, n++;
385  new_min_vcn = fr2->vcn + fr2->length;
386  } else {
387  length += cut_length, n++;
388  new_min_vcn = fr2->vcn + cut_length;
389  }
390  } else if(fr != fragments){
391  /* let's cut from the previous fragment */
392  if((fr->prev->length - cut_length) * jp->v_info.bytes_per_cluster \
393  < jp->udo.fragment_size_threshold){
394  vcn = fr->prev->vcn;
395  length += fr->prev->length, n++;
396  } else {
397  vcn = fr->prev->vcn + (fr->prev->length - cut_length);
398  length += cut_length, n++;
399  }
400  }
401  }
402  break;
403  }
404  if(fr->next == fragments) break;
405  }
406 
407 move_clusters:
408  /* move clusters */
409  if(length == 0 || n < 2){
410  min_vcn = max_vcn;
411  } else {
412  rgn = find_first_free_region(jp,0,length,NULL);
413  if(rgn){
414  if(move_file(file,vcn,length,rgn->lcn,jp) >= 0){
415  if(jp->udo.dbgprint_level >= DBG_DETAILED)
416  itrace("Defrag success for %ws",file->path);
417  defrag_succeeded = 1;
418  } else {
419  etrace("Defrag failure for %ws",file->path);
420  }
421  }
422  min_vcn = new_min_vcn;
423  }
424 
425  /* release list of fragments */
426  release_fragments_list(&fragments);
427  }
428  if(defrag_succeeded){
429  defragmented_files ++;
430  defragmented_partially ++;
431  moved_partially += (jp->pi.moved_clusters - x);
432  }
433  }
434  }
435 completed:
436  file->user_defined_flags |= UD_FILE_CURRENTLY_EXCLUDED;
437  file = next_file;
438  }
439 
440  /*
441  dtrace(">>> %I64u\\%I64u <<<",
442  jp->pi.processed_clusters,jp->pi.clusters_to_process);
443  */
444 
445  /* display amount of moved data and number of defragmented files */
446  itrace("%I64u files defragmented",defragmented_files);
447  itrace(" %I64u clusters moved",jp->pi.moved_clusters);
448  winx_bytes_to_hr(jp->pi.moved_clusters * jp->v_info.bytes_per_cluster,1,buffer,sizeof(buffer));
449  itrace(" %s moved",buffer);
450 
451  itrace("%I64u files defragmented entirely",defragmented_entirely);
452  itrace(" %I64u clusters moved",moved_entirely);
453  winx_bytes_to_hr(moved_entirely * jp->v_info.bytes_per_cluster,1,buffer,sizeof(buffer));
454  itrace(" %s moved",buffer);
455  itrace("%I64u files defragmented partially",defragmented_partially);
456  itrace(" %I64u clusters moved",moved_partially);
457  winx_bytes_to_hr(moved_partially * jp->v_info.bytes_per_cluster,1,buffer,sizeof(buffer));
458  itrace(" %s moved",buffer);
459 
460  /* cleanup */
461  clear_currently_excluded_flag(jp);
462 }
463 
468 static void defrag_sequence(udefrag_job_parameters *jp)
469 {
470  do {
471  if(jp->pi.fragmented == 0) return;
472  if(jp->termination_router((void *)jp)) return;
473  defrag_routine(jp);
474  } while(jp->pi.moved_clusters);
475 
476  /* defragment remaining files partially */
477  if(jp->udo.fragment_size_threshold == DEFAULT_FRAGMENT_SIZE_THRESHOLD){
478  jp->udo.fragment_size_threshold = PART_DEFRAG_MAGIC_CONSTANT;
479  jp->udo.algorithm_defined_fst = 1;
480  itrace("partial defragmentation: fragment size threshold = %I64u",
481  jp->udo.fragment_size_threshold);
482  do {
483  if(jp->pi.fragmented == 0) break;
484  if(jp->termination_router((void *)jp)) break;
485  defrag_routine(jp);
486  } while(jp->pi.moved_clusters);
487  jp->udo.fragment_size_threshold = DEFAULT_FRAGMENT_SIZE_THRESHOLD;
488  jp->udo.algorithm_defined_fst = 0;
489  }
490 }
491 
492 /************************************************************/
493 /* The entry point */
494 /************************************************************/
495 
505 int defragment(udefrag_job_parameters *jp)
506 {
507  int result;
508  struct prb_traverser t;
509  winx_file_info *file;
510  int second_attempt = 0;
511  ULONGLONG time;
512 
513  if(jp->job_type == DEFRAGMENTATION_JOB){
514  /* analyze the disk */
515  result = analyze(jp); /* we need to call it once, here */
516  if(result < 0) return result;
517  if(jp->termination_router((void *)jp)) return 0;
518  #ifdef TEST_SPECIAL_FILES_DEFRAG
519  test_special_files_defrag(jp);
520  return 0;
521  #endif
522  /* check fragmentation level */
523  if(!check_fragmentation_level(jp))
524  return 0;
525  /* reset counters */
526  jp->pi.processed_clusters = 0;
527  jp->pi.clusters_to_process = 0;
528  }
529 
530  time = start_timing("defragmentation",jp);
531 
532  /* do the job */
533  defrag_sequence(jp);
534 
535  /*
536  * Some files haven't been moved because target
537  * space turned out to be already in use. So,
538  * let's give those files another chance.
539  */
540  prb_t_init(&t,jp->fragmented_files);
541  file = prb_t_first(&t,jp->fragmented_files);
542  while(file){
543  if(jp->termination_router((void *)jp)) break;
544  if(is_moving_failed(file)){
545  second_attempt = 1;
546  file->user_defined_flags &= ~UD_FILE_MOVING_FAILED;
547  }
548  file = prb_t_next(&t);
549  }
550  if(second_attempt) defrag_sequence(jp);
551 
552  stop_timing("defragmentation",time,jp);
553  return 0;
554 }
555