search.c
Go to the documentation of this file.
1 /*
2  * UltraDefrag - a powerful defragmentation tool for Windows NT.
3  * Copyright (c) 2007-2013 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 
31 /*
32 * Ideas by Dmitri Arkhangelski <dmitriar@gmail.com>
33 * and Stefan Pendl <stefanpe@users.sourceforge.net>.
34 */
35 
36 #include "udefrag-internals.h"
37 
38 /************************************************************/
39 /* Free space region searching routines */
40 /************************************************************/
41 
50 winx_volume_region *find_first_free_region(udefrag_job_parameters *jp,
51  ULONGLONG min_lcn,ULONGLONG min_length,ULONGLONG *max_length)
52 {
53  winx_volume_region *rgn;
54  ULONGLONG time = winx_xtime();
55 
56  if(max_length) *max_length = 0;
57  for(rgn = jp->free_regions; rgn; rgn = rgn->next){
58  if(jp->termination_router((void *)jp)) break;
59  if(rgn->lcn >= min_lcn){
60  if(max_length){
61  if(rgn->length > *max_length)
62  *max_length = rgn->length;
63  }
64  if(rgn->length >= min_length){
65  jp->p_counters.searching_time += winx_xtime() - time;
66  return rgn;
67  }
68  }
69  if(rgn->next == jp->free_regions) break;
70  }
71  jp->p_counters.searching_time += winx_xtime() - time;
72  return NULL;
73 }
74 
83 winx_volume_region *find_last_free_region(udefrag_job_parameters *jp,
84  ULONGLONG min_lcn,ULONGLONG min_length,ULONGLONG *max_length)
85 {
86  winx_volume_region *rgn;
87  ULONGLONG time = winx_xtime();
88 
89  if(max_length) *max_length = 0;
90  if(jp->free_regions){
91  for(rgn = jp->free_regions->prev; rgn; rgn = rgn->prev){
92  if(jp->termination_router((void *)jp)) break;
93  if(rgn->lcn < min_lcn) break;
94  if(max_length){
95  if(rgn->length > *max_length)
96  *max_length = rgn->length;
97  }
98  if(rgn->length >= min_length){
99  jp->p_counters.searching_time += winx_xtime() - time;
100  return rgn;
101  }
102  if(rgn->prev == jp->free_regions->prev) break;
103  }
104  }
105  jp->p_counters.searching_time += winx_xtime() - time;
106  return NULL;
107 }
108 
109 #if 0
110 
122 winx_volume_region *find_matching_free_region(udefrag_job_parameters *jp,
123  ULONGLONG start_lcn, ULONGLONG min_length, int preferred_position)
124 {
125  winx_volume_region *rgn, *rgn_matching;
126  ULONGLONG length;
127  ULONGLONG time = winx_xtime();
128 
129  rgn_matching = NULL, length = 0;
130  for(rgn = jp->free_regions; rgn; rgn = rgn->next){
131  if(jp->termination_router((void *)jp)){
132  jp->p_counters.searching_time += winx_xtime() - time;
133  return NULL;
134  }
135  if(preferred_position == FIND_MATCHING_RGN_BACKWARD \
136  && rgn->lcn > start_lcn)
137  if(rgn_matching != NULL)
138  break;
139  if(rgn->length >= min_length){
140  if(length == 0 || rgn->length < length){
141  rgn_matching = rgn;
142  length = rgn->length;
143  if(length == min_length \
144  && preferred_position != FIND_MATCHING_RGN_FORWARD)
145  break;
146  }
147  }
148  if(rgn->next == jp->free_regions) break;
149  }
150  jp->p_counters.searching_time += winx_xtime() - time;
151  return rgn_matching;
152 }
153 #endif
154 
160 winx_volume_region *find_largest_free_region(udefrag_job_parameters *jp)
161 {
162  winx_volume_region *rgn, *rgn_largest;
163  ULONGLONG length;
164  ULONGLONG time = winx_xtime();
165 
166  rgn_largest = NULL, length = 0;
167  for(rgn = jp->free_regions; rgn; rgn = rgn->next){
168  if(jp->termination_router((void *)jp)){
169  jp->p_counters.searching_time += winx_xtime() - time;
170  return NULL;
171  }
172  if(rgn->length > length){
173  rgn_largest = rgn;
174  length = rgn->length;
175  }
176  if(rgn->next == jp->free_regions) break;
177  }
178  jp->p_counters.searching_time += winx_xtime() - time;
179  return rgn_largest;
180 }
181 
182 /************************************************************/
183 /* Auxiliary routines */
184 /************************************************************/
185 
189 struct file_block {
190  winx_file_info *file;
191  winx_blockmap *block;
192 };
193 
197 static int blocks_compare(const void *prb_a, const void *prb_b, void *prb_param)
198 {
199  struct file_block *a, *b;
200 
201  a = (struct file_block *)prb_a;
202  b = (struct file_block *)prb_b;
203 
204  if(a->block->lcn < b->block->lcn)
205  return (-1);
206  if(a->block->lcn == b->block->lcn)
207  return 0;
208  return 1;
209 }
210 
214 static void free_item (void *prb_item, void *prb_param)
215 {
216  struct file_block *item = (struct file_block *)prb_item;
217  winx_free(item);
218 }
219 
230 int create_file_blocks_tree(udefrag_job_parameters *jp)
231 {
232  trace(I"create_file_blocks_tree called");
233 
234  if(jp == NULL)
235  return (-1);
236 
237  if(jp->file_blocks)
239 
240  jp->file_blocks = prb_create(blocks_compare,NULL,NULL);
241  if(jp->file_blocks == NULL){
242  etrace("tree creation failed");
243  return (-1);
244  }
245  return 0;
246 }
247 
255 int add_block_to_file_blocks_tree(udefrag_job_parameters *jp, winx_file_info *file, winx_blockmap *block)
256 {
257  struct file_block *fb;
258  void **p;
259 
260  if(jp == NULL || file == NULL || block == NULL)
261  return (-1);
262 
263  if(jp->file_blocks == NULL)
264  return (-1);
265 
266  fb = winx_malloc(sizeof *fb);
267  if(fb == NULL){
269  return UDEFRAG_NO_MEM;
270  }
271 
272  fb->file = file;
273  fb->block = block;
274  p = prb_probe(jp->file_blocks,(void *)fb);
275  if(p == NULL){
276  winx_free(fb);
278  return UDEFRAG_NO_MEM;
279  }
280  /* if a duplicate item exists... */
281  if(*p != fb){
282  etrace("a duplicate found");
283  winx_free(fb);
284  }
285  return 0;
286 }
287 
294 int remove_block_from_file_blocks_tree(udefrag_job_parameters *jp, winx_blockmap *block)
295 {
296  struct file_block *fb;
297  struct file_block b;
298 
299  if(jp == NULL || block == NULL)
300  return (-1);
301 
302  if(jp->file_blocks == NULL)
303  return (-1);
304 
305  b.file = NULL;
306  b.block = block;
307  fb = prb_delete(jp->file_blocks,&b);
308  if(fb == NULL){
309  /* the following debugging output indicates either
310  a bug, or file system inconsistency */
311  etrace("failed for %p: VCN = %I64u, LCN = %I64u, LEN = %I64u",
312  block, block->vcn, block->lcn, block->length);
313  /* if block does not exist in tree, we have nothing to cleanup */
314  return 0;
315  }
316  winx_free(fb);
317  return 0;
318 }
319 
324 void destroy_file_blocks_tree(udefrag_job_parameters *jp)
325 {
326  trace(I"destroy_file_blocks_tree called");
327  if(jp){
328  if(jp->file_blocks){
329  prb_destroy(jp->file_blocks,free_item);
330  jp->file_blocks = NULL;
331  }
332  }
333 }
334 
335 /************************************************************/
336 /* File block searching routine */
337 /************************************************************/
338 
350 winx_blockmap *find_first_block(udefrag_job_parameters *jp,
351  ULONGLONG *min_lcn, int flags, winx_file_info **first_file)
352 {
353  winx_file_info *found_file, *file;
354  winx_blockmap *first_block, *block;
355  winx_blockmap b;
356  struct file_block fb, *item;
357  struct prb_traverser t;
358  int movable_file;
359  ULONGLONG lcn;
360  ULONGLONG tm = winx_xtime();
361 
362  if(jp == NULL || min_lcn == NULL || first_file == NULL)
363  return NULL;
364 
365  /* use fast binary tree search if possible */
366  if(jp->file_blocks == NULL) goto slow_search;
367  found_file = NULL; first_block = NULL;
368  b.lcn = *min_lcn; fb.block = &b;
369  prb_t_init(&t,jp->file_blocks);
370  item = prb_t_insert(&t,jp->file_blocks,&fb);
371  if(item == NULL){
372  /* insertion failed, let's go to the slow search */
373  itrace("slow search will be used");
374  goto slow_search;
375  }
376  if(item == &fb){
377  /* block at min_lcn not found */
378  item = prb_t_next(&t);
379  if(prb_delete(jp->file_blocks,&fb) == NULL){
380  /* removing failed, let's go to the slow search */
381  itrace("slow search will be used");
382  goto slow_search;
383  }
384  }
385  if(item){
386  found_file = item->file;
387  first_block = item->block;
388  }
389  while(!jp->termination_router((void *)jp)){
390  if(found_file == NULL) break;
391  if(flags & SKIP_PARTIALLY_MOVABLE_FILES){
392  movable_file = can_move_entirely(found_file,jp);
393  } else {
394  movable_file = can_move(found_file,jp);
395  }
396  if(is_file_locked(found_file,jp)) movable_file = 0;
397  if(movable_file){
398  if(jp->is_fat && is_directory(found_file) && first_block == found_file->disp.blockmap){
399  /* skip first fragments of FAT directories */
400  } else {
401  /* desired block found */
402  *min_lcn = first_block->lcn + 1; /* the current block will be skipped later anyway in this case */
403  *first_file = found_file;
404  jp->p_counters.searching_time += winx_xtime() - tm;
405  return first_block;
406  }
407  }
408 
409  /* skip current block */
410  *min_lcn = *min_lcn + 1;
411  /* and go to the next one */
412  item = prb_t_next(&t);
413  if(item == NULL) break;
414  found_file = item->file;
415  first_block = item->block;
416  }
417  *first_file = NULL;
418  jp->p_counters.searching_time += winx_xtime() - tm;
419  return NULL;
420 
421 slow_search:
422  if(jp->file_blocks) destroy_file_blocks_tree(jp);
423  while(!jp->termination_router((void *)jp)){
424  found_file = NULL; first_block = NULL; lcn = jp->v_info.total_clusters;
425  for(file = jp->filelist; file; file = file->next){
426  if(flags & SKIP_PARTIALLY_MOVABLE_FILES){
427  movable_file = can_move_entirely(file,jp);
428  } else {
429  movable_file = can_move(file,jp);
430  }
431  if(movable_file){
432  for(block = file->disp.blockmap; block; block = block->next){
433  if(block->lcn >= *min_lcn && block->lcn < lcn && block->length){
434  /* skip first fragments of FAT directories */
435  if(!jp->is_fat || !is_directory(file) || block != file->disp.blockmap){
436  found_file = file;
437  first_block = block;
438  lcn = block->lcn;
439  }
440  }
441  if(block->next == file->disp.blockmap) break;
442  }
443  }
444  if(file->next == jp->filelist) break;
445  }
446  if(found_file == NULL) break;
447  if(is_file_locked(found_file,jp)) continue;
448 
449  /* desired block found */
450  *min_lcn = first_block->lcn + 1; /* the current block will be skipped later anyway in this case */
451  *first_file = found_file;
452  jp->p_counters.searching_time += winx_xtime() - tm;
453  return first_block;
454  }
455  *first_file = NULL;
456  jp->p_counters.searching_time += winx_xtime() - tm;
457  return NULL;
458 }
459