1 #define _FILE_OFFSET_BITS 64
2 #include <sys/ioctl.h>
3 #include <unistd.h>
4 #include <fcntl.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <linux/fs.h>
8 #include <sys/mman.h>
9 #include <sys/stat.h>
10 #include <stdlib.h>
11
12 #ifndef FIBMAP
13 #define FIBMAP BMAP_IOCTL
14 #endif
15
16 struct lookup {
17 unsigned int l,p; /* logical block, physical block */
18 };
19
rsort(struct lookup * tab,unsigned long blocksperchunk)20 void rsort(struct lookup* tab,unsigned long blocksperchunk) {
21 struct lookup* x[2];
22 unsigned long i,j,c[2];
23 x[0]=(struct lookup*)malloc(blocksperchunk*sizeof(*tab));
24 x[1]=(struct lookup*)malloc(blocksperchunk*sizeof(*tab));
25 if (!x[0] || !x[1]) return;
26 for (i=1; i; i<<=1) {
27 c[0]=c[1]=0;
28 for (j=0; j<blocksperchunk; ++j) {
29 unsigned int idx=!!(tab[j].p&i);
30 x[idx][c[idx]]=tab[j];
31 ++c[idx];
32 }
33 if (c[0] && c[1]) {
34 memcpy(tab,x[0],c[0]*sizeof(tab[0]));
35 memcpy(tab+c[0],x[1],c[1]*sizeof(tab[0]));
36
37 #if 0
38 printf("\n%16lx mask, %lu zeros, %lu ones.\n\n",i,c[0],c[1]);
39 for (j=0; j<blocksperchunk; ++j)
40 printf("%16lx%s",tab[j].p,((j&15)==15)?"\n":" ");
41 printf("\n");
42 #endif
43
44 }
45 // printf("%16lx - %lu zeros, %lu ones\n",i,c[0],c[1]);
46 }
47 free(x[0]);
48 free(x[1]);
49 #if 0
50 for (i=1; i<blocksperchunk; ++i) {
51 if (tab[i-1].p > tab[i].p) {
52 printf("not sorted: %lu : %lu vs %lu\n",i-1,tab[i-1].p,tab[i].p);
53 exit(1);
54 }
55 }
56 #endif
57 }
58
59 static int dryrun;
60
61 volatile int x;
62
touch(const char * block)63 void touch(const char* block) {
64 x=*block;
65 }
66
myabs(long a)67 static unsigned long myabs(long a) {
68 return (a<0)?-a:a;
69 }
70
main(int argc,char * argv[])71 int main(int argc,char* argv[]) {
72 int fd=open(argv[1],O_RDONLY);
73 unsigned int block,i,blocks,chunk,chunks,cur,blocksleft,blocksdone,delta;
74 unsigned long long h1,h2;
75 struct stat s;
76 struct lookup *lt;
77
78 if (argc<2) {
79 fprintf(stderr,"usage: defrag filename > destination\n");
80 return 0;
81 }
82 if (fd<0) {
83 perror("open");
84 return 1;
85 }
86 if (fstat(fd,&s)) {
87 perror("fstat");
88 return 1;
89 }
90 blocks=s.st_size/s.st_blksize;
91 fprintf(stderr,"%u blocks, allocating look-up table\n",blocks);
92 lt=(struct lookup*)malloc(blocks*sizeof(struct lookup));
93 if (!lt) {
94 perror("malloc");
95 return 1;
96 }
97 h1=h2=0;
98 for (i=0; i<blocks; i++) {
99 block=i;
100 if (ioctl(fd,FIBMAP,&block)) {
101 perror("ioctl FIBMAP");
102 return 1;
103 }
104 if (!block) {
105 fprintf(stderr,"block is zero!\n");
106 return 1;
107 }
108 lt[i].l=i; lt[i].p=block;
109 if (i) h1+=myabs(lt[i].p-lt[i-1].p);
110 }
111
112 /* the next step is to sort the look-up table so that we read in
113 * ascending block order. However, we don't handle the whole table at
114 * once, only 128M at a time. */
115
116 chunks=(s.st_size+128*1024*1024-1)/(128*1024*1024); cur=0;
117 fprintf(stderr,"populated look-up table, %u chunks\n",chunks);
118 dryrun=isatty(1);
119 blocksleft=blocks; blocksdone=0;
120 for (chunk=0; chunk<chunks; ++chunk) {
121 int blocksperchunk;
122 unsigned long chunksize=128*1024*1024;
123 char* map=0;
124 if (!dryrun)
125 fprintf(stderr,"chunk %u/%u [%luMB]: ",
126 chunk+1,chunks,chunksize/(1024*1024)); fflush(stderr);
127 if (chunksize>blocksleft*s.st_blksize) {
128 delta=blocksleft;
129 chunksize=s.st_size-blocksdone*s.st_blksize;
130 } else
131 delta=chunksize/s.st_blksize;
132 blocksleft-=delta;
133 if (!dryrun) {
134 map=mmap(0,chunksize,PROT_READ,MAP_SHARED,fd,blocksdone*s.st_blksize);
135 if (map==(char*)-1) {
136 perror("mmap");
137 return 1;
138 }
139 madvise(map,chunksize,MADV_RANDOM); /* tell the OS not to read ahead */
140 }
141
142 /* how many blocks are in this chunk? */
143 blocksperchunk=chunksize/s.st_blksize;
144
145 rsort(lt+cur,blocksperchunk);
146 for (i=0; i<blocksperchunk; ++i) {
147 if (!dryrun && !(i%100)) {
148 int j;
149 fprintf(stderr,"\rchunk %u/%u [%luMB]: reading block %u/%u... ",
150 chunk+1,chunks,chunksize/(1024*1024),i,blocksperchunk);
151 for (j=0; j<i; ++j)
152 touch(map+((lt[cur+j].l-blocksdone)*s.st_blksize));
153 }
154 if (cur+i) h2+=myabs(lt[cur+i].p-lt[cur+i-1].p);
155 if (!dryrun)
156 touch(map+((lt[cur+i].l-blocksdone)*s.st_blksize));
157 }
158 if (!dryrun) {
159 fprintf(stderr,"\rchunk %u/%u [%luMB]: read all %u blocks; writing... ",
160 chunk+1,chunks,chunksize/(1024*1024),blocksperchunk);
161 write(1,map,chunksize);
162 fsync(1);
163 fprintf(stderr,"\n");
164 munmap(map,chunksize);
165 }
166
167 cur+=blocksperchunk;
168 blocksdone+=delta;
169 }
170 if (dryrun)
171 fprintf(stderr,"head movement can be reduced from %llu to %llu (%d percent savings)\n",
172 h1,h2,(int)(100-(h2*100/h1)));
173 else
174 fprintf(stderr,"reduced head movements from %llu to %llu (%d percent saved)\n",
175 h1,h2,(int)(100-(h2*100/h1)));
176
177 return 0;
178 }
179