- python does not export variables beginning with underscore
[util-vserver.git] / python / vduimpl.c
1 /* Copyright 2005 Princeton University */
2
3 #include <Python.h>
4
5 #define _LARGEFILE64_SOURCE 1
6
7 #include <stdlib.h>
8 #include <stdio.h>
9 #include <sys/stat.h>
10 #include <sys/types.h>
11 #include <fcntl.h>
12 #include <unistd.h>
13 #include <dirent.h>
14 #include <errno.h>
15 #include <string.h>
16 #include <sys/ioctl.h>
17 #include <assert.h>
18
19
20 /*
21  * hash table implementation
22  */
23
24 typedef ino64_t KEY;
25 typedef KEY *PKEY;
26 typedef struct stat64 VAL;
27 typedef VAL *PVAL;
28
29 static inline
30 unsigned int
31 HASH(PKEY key){
32         return (int) *key;
33 }
34
35 static inline
36 unsigned int // boolean
37 EQUAL(PKEY key1, PKEY key2){
38         return *key1 == *key2;
39 }
40
41 #ifndef MIN
42 #define MIN(x,y) (((x)<(y))?(x):(y))
43 #endif // MIN
44
45 #ifndef MAX
46 #define MAX(x,y) (((x)>(y))?(x):(y))
47 #endif // MAX
48
49
50 /*
51  * hash table support for efficient lookup of duplicate inodes
52  */
53
54 #define Multiplier  (0x9e3779b9)
55 #define MaxLogBuckets  (((sizeof (unsigned long))*8) - 2)
56 #define MaxBuckets     (1<<MaxLogBuckets)
57 #define MinLogBuckets  (4)
58 #define MinBuckets     (1<<MinLogBuckets)
59
60 /* Thresholds for rehashing the table: *)
61  * to avoid crazy oscillations, we must have MaxDensity > 2*MinDensity; *)
62  * to avoid excessive probes, we must try to keep MaxDensity low. *)
63  * Divide by 100 before using
64  */
65 #define MaxDensity 75 /* max numEntries/NUMBER(buckets) */
66 #define MinDensity 20 /* min numEntries/NUMBER(buckets) */
67 #define IdealDensity 50
68 #define BITSIZE(x) (sizeof(x)*8)
69
70 #define NEW(type,num) ((type*)malloc(sizeof(type)*num))
71 #define DISPOSE(ptr) (free((void*)ptr))
72
73 /*
74  * Generic Hash Entry Type
75  */
76
77 typedef struct VoidList {
78         struct VoidList *tail;
79 } VoidList, *PVoidList;
80
81 typedef struct HashTable {
82         PVoidList *buckets;
83         unsigned int numBuckets;    // number of buckets
84         unsigned int minLogBuckets; // minimum value for Log_2(initial size) 
85         unsigned int logBuckets;    // CEILING(Log2(NUMBER(buckets^))) 
86         unsigned int maxEntries;    // maximum number of entries 
87         unsigned int minEntries;    // minimum number of entries 
88         unsigned int numEntries;    // current num of entries in table 
89         PVoidList cache;            // cache of removed elements 
90         int cacheSize;              // current size of the cache 
91         int maxCacheSize;           // maximum size, -1 means unbounded, 0 no cache 
92 } HashTable, *PHashTable;
93
94 /*
95  * Hash Prototypes
96  */
97
98 PHashTable
99 Init(PHashTable tbl, unsigned int n, int maxCacheSize);
100
101 void
102 Dispose(PHashTable tbl);
103
104 unsigned int
105 Log_2(unsigned int x);
106
107 void
108 NewBuckets(PHashTable tbl, unsigned int logBuckets);
109
110 /*
111  * Generic Hash Table support
112  */
113
114 PHashTable
115 Init(PHashTable tbl, unsigned int n, int maxCacheSize){
116         int idealBuckets;
117         int minBuckets;
118   
119         idealBuckets = MIN(((n*100)/IdealDensity),MaxBuckets);
120         minBuckets = MAX(MinBuckets, idealBuckets);
121         tbl->minLogBuckets = Log_2(minBuckets);
122
123         NewBuckets(tbl, tbl->minLogBuckets);
124         tbl->numEntries = 0;
125         tbl->maxCacheSize = maxCacheSize;
126         tbl->cacheSize = 0;
127         tbl->cache = 0;
128         return tbl;
129 } // Init()
130
131
132 /*
133  * Internal procedures
134  */
135
136 unsigned int
137 Log_2(unsigned int x){
138         /* return CEILING(LOG_2(x)) */
139         unsigned int log = 0;
140         unsigned int n= 1;
141
142         assert(x != 0);
143         while ((log < MaxLogBuckets) && (x > n)){
144                 log++; 
145                 n += n;
146         }
147         return log;
148 }
149
150 void
151 NewBuckets(PHashTable tbl, unsigned int logBuckets){
152         /* Allocate "2^logBuckets" buckets. */
153         unsigned int numBuckets = 1 << logBuckets;
154         PVoidList *b;
155         unsigned int i;
156
157         tbl->buckets = NEW(PVoidList, numBuckets);
158         tbl->numBuckets = numBuckets;
159         b = tbl->buckets;
160
161         for (i=0; i<tbl->numBuckets; i++){
162                 b[i] = NULL;
163         }
164         tbl->logBuckets = logBuckets;
165         tbl->maxEntries = MaxDensity * numBuckets / 100;
166         tbl->minEntries = MinDensity * numBuckets / 100;
167 }
168
169 #ifndef NULL
170 #define NULL (void*)0
171 #endif
172
173 #ifndef TRUE
174 #define TRUE 1
175 #endif
176
177 #ifndef FALSE
178 #define FALSE 0
179 #endif
180
181 /*
182  * Type specific hash entry
183  */
184 typedef struct EntryList {
185         struct EntryList *tail;
186         KEY key;
187         VAL val;
188 }EntryList, *PEntryList;
189
190 /*
191  * Type specific Hash implementation functions
192  */
193
194 static
195 void
196 Rehash(PHashTable tbl, unsigned int logBuckets) {
197         /* Reallocate "2^logBuckets" buckets, and rehash the entries into
198          * the new table.
199          */
200
201         PVoidList *oldBucketPointer;
202         PEntryList *ob, obi;
203         PEntryList *nb, *nbh;
204         PEntryList that, tail;
205         unsigned int index; 
206         unsigned int i;
207         unsigned int oldNumBuckets;
208
209         return;
210         assert(logBuckets <= MaxLogBuckets);
211         assert(logBuckets >= tbl->minLogBuckets);
212         oldBucketPointer = tbl->buckets;
213         ob = (PEntryList*)tbl->buckets;
214         oldNumBuckets = tbl->numBuckets;
215
216         NewBuckets(tbl, logBuckets);
217         nb = (PEntryList*)tbl->buckets;
218
219         for(i=0;i<oldNumBuckets;i++){
220                 obi = ob[i];
221                 that = obi;
222                 while (that != NULL) {
223                         index = (HASH(&(that->key))*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
224                         nbh = &(nb[index]);
225                         tail = that->tail;
226                         that->tail = *nbh;
227                         *nbh = that;
228                         that = tail;
229                 }
230         }
231         DISPOSE (oldBucketPointer);
232 }
233
234 static inline
235 unsigned int /* boolean */
236 Get(PHashTable tbl, PKEY key, PVAL *val){
237         PEntryList that;
238         unsigned int index;
239
240         index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
241         that = (PEntryList)tbl->buckets[index];
242         while ((that != NULL) && !EQUAL(key,&(that->key))) {
243                 that = that->tail;
244         }
245         if (that != NULL){
246                 *val = &that->val;
247                 return TRUE;
248         }
249         else {
250                 return FALSE;
251         }
252 }
253
254 static inline 
255 unsigned int /* boolean */
256 Put(PHashTable tbl, PKEY key, PVAL *val){
257         PEntryList that;
258         PEntryList *first;
259         unsigned int index;
260         unsigned int res;
261
262         index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
263         first = (PEntryList*)&(tbl->buckets[index]);
264         that = *first;
265         while ((that != NULL) && !EQUAL(key, &(that->key))){
266                 that = that->tail;
267         }
268   
269         /* found an entry in the hash table given above key */
270         if (that != NULL){
271                 res = TRUE;
272         }
273         else {
274                 /* check if we can reuse something from the cache */
275                 if (tbl->cache != NULL) {
276                         that = (PEntryList)tbl->cache;
277                         tbl->cache = (PVoidList)tbl->cache->tail;
278                         that->key = *key;
279                         that->tail = *first;
280                         *first = that;
281                 }
282                 else {
283                         that = NEW(EntryList,1);
284                         that->key = *key;
285                         that->tail = *first;
286                         *first = that;
287                 }
288                 that->val = **val;
289
290                 tbl->numEntries++;
291                 if ((tbl->logBuckets < MaxLogBuckets)
292                     && (tbl->numEntries > tbl->maxEntries)){
293                         Rehash(tbl, tbl->logBuckets + 1); /* too crowded */
294                 }
295                 res = FALSE;
296         }
297         *val = &that->val;
298         return res;
299
300 }
301
302 static inline
303 int
304 Delete(PHashTable tbl,PKEY key){
305         PEntryList that, prev;
306         PEntryList *first;
307         unsigned int index;
308
309         index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
310         first = (PEntryList*)&(tbl->buckets[index]);
311         that = *first;
312         prev = NULL;
313
314         while ((that != NULL) && !EQUAL(key, &(that->key))){
315                 prev = that;
316                 that = that->tail;
317         }
318         if (that != NULL) {
319                 if (prev == NULL) {
320                         *first = that->tail;
321                 }
322                 else {
323                         prev->tail = that->tail;
324                 }
325                 if ((tbl->maxCacheSize == -1)||(tbl->cacheSize < tbl->maxCacheSize)) {
326                         that->tail = (PEntryList)tbl->cache;
327                         tbl->cache = (PVoidList)that;
328                         tbl->cacheSize++;
329                 }
330                 else {
331                         DISPOSE (that);
332                 }
333                 tbl->numEntries--;
334                 if (tbl->maxCacheSize == 0) {
335                         if ((tbl->logBuckets > tbl->minLogBuckets)
336                             && (tbl->numEntries < tbl->minEntries)) {
337                                 Rehash(tbl, tbl->logBuckets - 1); /* too sparse */
338                         }
339                 }
340                 return TRUE;
341         }
342         else {
343                 return FALSE;
344         }
345 }
346
347 typedef void (*callback)(PKEY key, PVAL val);
348
349 void
350 Iterate(PHashTable tbl, callback fn)
351 {
352         PVoidList that;
353         unsigned int i;
354   
355         for(i=0;i<tbl->numBuckets;i++) {
356                 that = tbl->buckets[i];
357                 while ( that != (PVoidList)0 ) {
358                         PEntryList entry = (PEntryList)that;
359                         fn(&entry->key,&entry->val);
360                         that = that->tail;
361                 }
362         }
363 }
364
365 void
366 Dispose(PHashTable tbl)
367 {
368         PVoidList that, next;
369         unsigned int i;
370
371         for(i=0;i<tbl->numBuckets;i++) {
372                 that = tbl->buckets[i];
373                 while( that != NULL) {
374                         next = that->tail;
375                         DISPOSE (that);
376                         tbl->numEntries--;
377                         that = next;
378                 }
379         }
380         DISPOSE(tbl->buckets);
381         assert(tbl->numEntries = 0);
382 }
383
384 static int /* boolean */
385 INOPut(PHashTable tbl, ino64_t* key, struct stat64 **val){
386         return Put(tbl, key, val);
387 }
388
389 __extension__ typedef long long         longlong;
390
391 struct stats {
392         longlong inodes;
393         longlong blocks;
394         longlong size;
395 };
396
397 static short verbose = 0;
398
399 static int vdu_onedir (PHashTable tbl, struct stats *__s, char const *path)
400 {
401         char const *foo = path;
402         struct stat64 dirst, st;
403         struct dirent *ent;
404         char *name;
405         DIR *dir;
406         int dirfd;
407         int res = 0;
408         longlong dirsize, dirinodes, dirblocks;
409
410         dirsize = dirinodes = dirblocks = 0;
411
412         // A handle to speed up chdir
413         if ((dirfd = open (path,O_RDONLY)) == -1) {
414                 return -1;
415         }
416
417         if (fchdir (dirfd) == -1) {
418                 return -1;
419         }
420
421         if (fstat64 (dirfd,&dirst) != 0) {
422                 return -1;
423         }
424
425         if ((dir = opendir (".")) == NULL) {
426                 return -1;
427         }
428
429         /* Walk the directory entries and compute the sum of inodes,
430          * blocks, and disk space used. This code will recursively descend
431          * down the directory structure. 
432          */
433
434         while ((ent=readdir(dir))!=NULL){
435                 if (lstat64(ent->d_name,&st)==-1){
436                         continue;
437                 }
438         
439                 dirinodes ++;
440
441                 if (S_ISREG(st.st_mode)){
442                         if (st.st_nlink > 1){
443                                 struct stat64 *val;
444                                 int nlink;
445
446                                 /* Check hash table if we've seen this inode
447                                  * before. Note that the hash maintains a
448                                  * (inode,struct stat) key value pair.
449                                  */
450
451                                 val = &st;
452
453                                 (void) INOPut(tbl,&st.st_ino,&val);
454
455                                 /* Note that after the INOPut call "val" refers to the
456                                  * value entry in the hash table --- not &st.  This
457                                  * means that if the inode has been put into the hash
458                                  * table before, val will refer to the first st that
459                                  * was put into the hashtable.  Otherwise, if it is
460                                  * the first time it is put into the hash table, then
461                                  * val will be equal to this &st.
462                                  */
463                                 nlink = val->st_nlink;
464                                 nlink --;
465
466                                 /* val refers to value in hash tbale */
467                                 if (nlink == 0) {
468
469                                         /* We saw all hard links to this particular inode
470                                          * as part of this sweep of vdu. So account for
471                                          * the size and blocks required by the file.
472                                          */
473
474                                         dirsize += val->st_size;
475                                         dirblocks += val->st_blocks;
476
477                                         /* Do not delete the (ino,val) tuple from the tbl,
478                                          * as we need to handle the case when we are
479                                          * double counting a file due to a bind mount.
480                                          */
481                                         val->st_nlink = 0;
482
483                                 } else if (nlink > 0) {
484                                         val->st_nlink = nlink;
485                                 } else /* if(nlink < 0) */ {
486                                         /* We get here when we are double counting nlinks
487                                            due a bind mount. */
488
489                                         /* DO NOTHING */
490                                 }
491                         } else {
492                                 dirsize += st.st_size;
493                                 dirblocks += st.st_blocks;
494                         }
495
496                 } else if (S_ISDIR(st.st_mode)) {
497                         if ((st.st_dev == dirst.st_dev) &&
498                             (strcmp(ent->d_name,".")!=0) &&
499                             (strcmp(ent->d_name,"..")!=0)) {
500
501                                 dirsize += st.st_size;
502                                 dirblocks += st.st_blocks;
503
504                                 name = strdup(ent->d_name);
505                                 if (name==0) {
506                                         return -1;
507                                 }
508                                 res |= vdu_onedir(tbl,__s,name);
509                                 free(name);
510                                 fchdir(dirfd);
511                         }
512                 } else {
513                         /* dirsize += st.st_size; */
514                         /* dirblocks += st.st_blocks; */
515                 }
516         }
517         closedir (dir);
518         close (dirfd);
519         __s->inodes += dirinodes;
520         __s->blocks += dirblocks;
521         __s->size   += dirsize;
522         if (verbose) {
523                 printf("%16lld %16lld %16lld %s\n",dirinodes, dirblocks, dirsize,foo);
524                 printf("%16lld %16lld %16lld %s\n",__s->inodes, __s->blocks, __s->size,foo);
525         }
526
527         return res;
528 }
529
530
531 static PyObject *
532 do_vdu(PyObject *self, PyObject *args)
533 {
534         PyObject *tuple;
535
536         const char *path;
537         int res;
538         struct stats s;
539         HashTable tbl;
540
541         if (!PyArg_ParseTuple(args, "s", &path))
542                 return Py_None;
543
544         /* init of tbl and stats */
545         s.inodes = s.blocks = s.size = 0;
546         (void) Init(&tbl,0,0);
547
548         res = vdu_onedir(&tbl, &s, path);
549
550         /* deallocate whatever has been added to tbl */
551         Dispose(&tbl);
552
553         /* create a python (inode, block, size) tuple */
554         tuple = Py_BuildValue("(L,L,L)",
555                               s.inodes,
556                               s.blocks>>1, /* NOTE: div by 2 to adjust
557                                             * 512b block count to 1K
558                                             * block count 
559                                             */
560                               s.size);
561         return (res == -1) ? PyErr_SetFromErrno(PyExc_OSError) : tuple;
562 }
563
564 static PyMethodDef  methods[] = {
565         { "vdu", do_vdu, METH_VARARGS,
566           "perform vdu operation on directory tree" },
567         { NULL, NULL, 0, NULL }
568 };
569
570 PyMODINIT_FUNC
571 initvduimpl(void)
572 {
573         Py_InitModule("vduimpl", methods);
574 }