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         int  cwd_fd;
 541
 542         if (!PyArg_ParseTuple(args, "s", &path))
 543                 return Py_None;
 544
 545         /* init of tbl and stats */
 546         s.inodes = s.blocks = s.size = 0;
 547         (void) Init(&tbl,0,0);
 548
 549         cwd_fd = open(".", O_RDONLY);
 550         res = vdu_onedir(&tbl, &s, path);
 551         fchdir(cwd_fd);
 552         close(cwd_fd);
 553
 554         /* deallocate whatever has been added to tbl */
 555         Dispose(&tbl);
 556
 557         /* create a python (inode, block, size) tuple */
 558         tuple = Py_BuildValue("(L,L,L)",
 559                               s.inodes,
 560                               s.blocks>>1, /* NOTE: div by 2 to adjust
 561                                             * 512b block count to 1K
 562                                             * block count
 563                                             */
 564                               s.size);
 565         return (res == -1) ? PyErr_SetFromErrno(PyExc_OSError) : tuple;
 566 }
 567
 568 static PyMethodDef  methods[] = {
 569         { "vdu", do_vdu, METH_VARARGS,
 570           "perform vdu operation on directory tree" },
 571         { NULL, NULL, 0, NULL }
 572 };
 573
 574 PyMODINIT_FUNC
 575 initvduimpl(void)
 576 {
 577         Py_InitModule("vduimpl", methods);
 578 }