Path: katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Message-ID: Date: 12 Apr 1994 09:51:03 GMT Organization: Software Research Associates, Inc.,Japan Newsgroups: fj.unix,fj.news.adm Subject: a statistics about monotonic growth of directories on FFS Distribution: fj 　Fast File System(BSD のファイルシステム)およびそれに由来するファイル システムでは、ディレクトリのサイズは決して縮小されることはありません。 つまり、ディレクトリが生成されてから現在までの間で、最もディレクトリが 膨らんだ瞬間の領域がそのまま保持されています。平常時とピーク時のファイ ル数の差が激しいディレクトリや、一時的に多くの長いファイル名のファイル を保持した経験を持つディレクトリでは、ディレクトリによってディスクブロッ クが無駄使いされている可能性があります。 　このことが、長期間に渡って運用されるファイルシステムにどのような影響 を及ぼすのかに興味を持ったので、400M ほどあるニューススプールを例にとっ て、ディレクトリファイルの無駄がどのように変化するのか、９ヶ月ほどの間 簡単な統計をとってみました。 　ディレクトリの無駄を計算する dirwaste というプログラムと、それを使っ てニューススプール内のディレクトリがどれだけ無駄を含んでいるか日々調べ た結果の statistics というファイルを投稿します。X の環境で make xgraph すると、問題のニューススプールの無駄がどう変化したのか観察できます。参 考のために、そのときのスプールの空き容量と対比するかたちにしてみました。 　短期的には、ディスクの空きが多い（多分ファイルが少ない）と無駄が多い ことが確認できます。alt, comp のような流量の大きいグループは expire が １週間より短かったこともあって、ディレクトリの無駄は日々のニュースの流 量（週末に減る）に大きく影響を受け、規則的に変化しているのが読み取れる と思います。 　長期的には徐々に増加していますが、ニュースグループの増加の影響を受け ずにどこかで飽和するのか、それとも現在のように活発に日々新しいニュース グループができることによって永遠に増加し続けるのか不明です。 　年末年始の時期には、数日間ディスクの無駄（と空き）が大きく増えている のも見て取れます。 -- 渡邊克宏＠ＳＲＡ #!/bin/sh # This is a shell archive (produced by shar 3.49) # To extract the files from this archive, save it to a file, remove # everything above the "!/bin/sh" line above, and type "sh file_name". # # made 04/12/1994 09:07 UTC by katsu@sran14 # Source directory /var/home/mmb/katsu/hack/dirwaste # # existing files will NOT be overwritten unless -c is specified # # This shar contains: # length mode name # ------ ---------- ------------------------------------------ # 3456 -r--r--r-- README # 504 -r--r--r-- Makefile # 396 -r--r--r-- dirsize.c # 5103 -r--r--r-- dirwaste.c # 4485 -rw-r--r-- statistics # # ============= README ============== if test -f 'README' -a X"$1" != X"-c"; then echo 'x - skipping README (File already exists)' else echo 'x - extracting README (Text)' sed 's/^X//' << 'SHAR_EOF' > 'README' && $Id: README,v 1.6 1994/04/12 09:04:46 katsu Exp $ X X　dirwaste は渡邊克宏 が書きました。Public Domain です。 X X　BSD の FFS ではディレクトリファイルが小さくなることがありません。ファ Xイルを沢山消した後などには、空洞のように残った空きエントリのために、ディ Xレクトリファイルがディスクブロックを無駄使いしていることがありえます。 dirwaste は、こうした無駄がディレクトリにどれだけ含まれているかを調べ Xるコマンドです。実行ファイルを作るには make してください。 Xがないシステムでは、CFLAGS=-DNO_DIRENT をつけて make してください。 X X使い方: dirwaste ディレクトリ名 X X例： X n14:17% cd /tmp n14:18% ls -lA total 10 drwxrwxrwx 2 katsu staff 512 Apr 10 09:23 .X11-unix/ -rw-r--r-- 1 katsu staff 176 Apr 11 14:53 j drwxr-xr-x 2 root wheel 8192 Nov 4 1991 lost+found/ n14:19% dirwaste . X real packed wasted filesys ./lost+found ignored. X 512 512 0 0 ./.X11-unix X 19456 512 18944 18432 . total wasted: 18944 bytes, or 18432 bytes in filesystem. X real: 実際のディレクトリのサイズ packed: もしディレクトリに空のエントリがなかったとしたときに X 推測されるディレクトリのサイズ wasted: = real - packed filesys: fragment size を単位にしてディスク領域が割り当てられ X ることを意識して、もしディレクトリに空のエントリがな X かったとしたときに、現在と比べてどれだけの領域がファ X イルシステム上で節約できるのかという値。実質的な無駄 X を表現している。wasted を fragment size で切り上げし X たものではない。 X X X　サブディレクトリに UFS のマウントポイントがあっても動きますが、NFS Xマウントしているとうまく動かないこともありえます。 X　あんまり沢山無駄があった場合、dump/restore や tar で一旦待避してから Xディレクトリを作り直すと、少しディスクブロックがもうかるはずです。上の X例の場合、18432 bytes もうかることが期待できます。 X X X　付属している statistics というファイルは、ニューススプール (大きさ 409167KB) に使われているディレクトリ群がどのくらいディスクを無駄使いし Xているかを、dirwaste を使って、1993/May/16th から、1994/Jan/30th まで X日を追って調べた例です。問題のニューススプールは、1993/May/15th に一旦 newfs した後で restore しなおし、その時点の記事でほぼ満杯にしました。 X　最初のフィールドは 1993/May/16th からの日にち、次のフィールドは directory が無駄に使っている領域(Byte 単位)、最後のフィールドは ディス Xクパーティションの残り容量(KByte 単位)となっています。X 環境で X make xgraph Xすると、xgraph に表示することができます。 X　短期的には、ディスクの空きが多い（多分ファイルが少ない）と無駄が多い Xように見えます。alt, comp のような流量の大きいグループは expire が１週 X間より短かったので、ディレクトリの無駄は日々のニュースの流量（週末に減 Xる）に大きく影響を受け、規則的に変化しているのが読み取れると思います。 X　長期的には徐々に増加していますが、ニュースグループの増加の影響を受け Xずにどこかで飽和するのか、それとも現在のように活発に日々新しいニュース Xグループができることによって永遠に増加し続けるのか不明です。 X　220 日目ぐらいから数日間ディスクの無駄と空きが大きく増えているのは、 X年末年始の休み（特に海外）の影響です。 SHAR_EOF chmod 0444 README || echo 'restore of README failed' Wc_c="`wc -c < 'README'`" test 3456 -eq "$Wc_c" || echo 'README: original size 3456, current size' "$Wc_c" fi # ============= Makefile ============== if test -f 'Makefile' -a X"$1" != X"-c"; then echo 'x - skipping Makefile (File already exists)' else echo 'x - extracting Makefile (Text)' sed 's/^X//' << 'SHAR_EOF' > 'Makefile' && # # $Id: Makefile,v 1.2 1994/04/11 09:55:45 katsu Exp $ # X # # If your system doesn't have , please make with CFLAGS=-DNO_DIRENT. # #CFLAGS= -DNO_DIRENT X dirwaste: dirwaste.o dirsize.o X $(CC) -o dirwaste dirwaste.o dirsize.o X xgraph: statistics X ( ¥ X echo "XUnitText: days" ;¥ X echo "YUnitText: bytes" ;¥ X echo '"dir wastes"'; ¥ X awk '{print $$1, $$2}' statistics; ¥ X echo ""; ¥ X echo '"diskfree/1024"'; ¥ X awk '{print $$1, $$3}' statistics ¥ X ) | xgraph X clean: X -rm -f *.o dirwaste X SHAR_EOF chmod 0444 Makefile || echo 'restore of Makefile failed' Wc_c="`wc -c < 'Makefile'`" test 504 -eq "$Wc_c" || echo 'Makefile: original size 504, current size' "$Wc_c" fi # ============= dirsize.c ============== if test -f 'dirsize.c' -a X"$1" != X"-c"; then echo 'x - skipping dirsize.c (File already exists)' else echo 'x - extracting dirsize.c (Text)' sed 's/^X//' << 'SHAR_EOF' > 'dirsize.c' && /* X $Id: dirsize.c,v 1.2 1994/04/11 05:44:39 katsu Exp $ */ X #include #include X /* X dent_minsize_namelen: X return the minimum amount of space in directory file required to represent X a directory entry whose name length == len. */ int dent_minsize_namelen(len) int len; { X struct direct fs_dirent; X X fs_dirent.d_namlen = len; X return DIRSIZ(&fs_dirent); } SHAR_EOF chmod 0444 dirsize.c || echo 'restore of dirsize.c failed' Wc_c="`wc -c < 'dirsize.c'`" test 396 -eq "$Wc_c" || echo 'dirsize.c: original size 396, current size' "$Wc_c" fi # ============= dirwaste.c ============== if test -f 'dirwaste.c' -a X"$1" != X"-c"; then echo 'x - skipping dirwaste.c (File already exists)' else echo 'x - extracting dirwaste.c (Text)' sed 's/^X//' << 'SHAR_EOF' > 'dirwaste.c' && /* X Figure out how many blocks are wasted by eliminated entries on directory. X X Public Domain Software written by WATANABE Katsuhiro . X Bugs: X It can happen that this doesn't work on NFS mounted directories, X because cannot figure out dirblksiz correctly. X X $Id: dirwaste.c,v 1.4 1994/04/11 05:46:23 katsu Exp $ */ X #include #include #include #include #include #include #include #include #include #include X #ifdef NO_DIRENT #include typedef struct direct DIRENT; #else #include typedef struct dirent DIRENT; #endif X char *myname; int dirblksiz; /* size of directory chunk */ static int total_wasted, total_fs_wasted; X char *emalloc(); X main(argc, argv) int argc; char **argv; { X myname = argv[0]; X /* X The header file which defines DIRBLKSIZ varies OS to OS. */ #ifdef DIRBLKSIZ X dirblksiz = DIRBLKSIZ; #else X { X static char nameprefix[] = "/tmp/dirwaste"; X char *tempname; X struct stat statbuf; X X tempname = emalloc(strlen(nameprefix) + strlen(myname) + 6 + 1); X strcpy(tempname, nameprefix); X strcat(tempname, "XXXXXX"); X mktemp(tempname); X if (mkdir(tempname, 0777)) { X perror(tempname); X exit(1); X } X if (stat(tempname, &statbuf)) { X perror(tempname); X exit(2); X } X rmdir(tempname); X free(tempname); X dirblksiz = (int)statbuf.st_size; X } #endif X if (argc != 2) { X fprintf(stderr, "Usage: %s directory¥n", myname); X exit(3); X } X printf(" real packed wasted filesys¥n"); X X total_fs_wasted = total_wasted = 0; X list_dir_wastes(argv[1]); X printf("total wasted: %d bytes, or %d bytes in filesystem.¥n", X total_wasted, total_fs_wasted); X exit(0); } X X #define isMyself(dirname) (!strcmp((dirname), ".")) #define isMyParent(dirname) (!strcmp((dirname), "..")) #define isDirectory(status) (((status).st_mode & S_IFMT) == S_IFDIR) #define isLostFound(status) ((status).st_ino == LOSTFOUNDINO) X list_dir_wastes(dirname) char *dirname; { X DIR *dirp; X DIRENT *entp; X struct stat statbuf; X struct statfs statfsbuf; X X int entrysize; X char *ename, *efullname; X int fs_blocksize, fs_fragsize; X int dirsize, chunks, dirsize_real, wasted; X int fs_dirsize, fs_dirsize_real, fs_wasted; X X if ((dirp = opendir(dirname)) == (DIR *)NULL) { X fprintf(stderr, "%s cannot open as a directory. ignored.¥n", dirname); X return; X } X dirsize = 0; X chunks = 0; X while ((entp = readdir(dirp)) != (DIRENT *)NULL) { X entrysize = dent_minsize(entp); X if (dirsize + entrysize > chunks * dirblksiz) { X dirsize = chunks++ * dirblksiz + entrysize; X } else { X dirsize += entrysize; X } X ename = entp->d_name; X efullname = emalloc(strlen(dirname) + 1 + strlen(entp->d_name) + 1); X if (dirname[strlen(dirname) - 1] == '/') { X sprintf(efullname, "%s%s", dirname, ename); X } else { X sprintf(efullname, "%s/%s", dirname, ename); X } X if (lstat(efullname, &statbuf)) { X fprintf(stderr, X "%s cannot lstat. assume not to be a directory.¥n", X dirname); X } else { X if (isDirectory(statbuf) && X !isMyself(ename) && !isMyParent(ename)) { X if (isLostFound(statbuf)) { X fprintf(stderr, "%s ignored.¥n", efullname); X } else { X list_dir_wastes(efullname); X } X } X } X free(efullname); X } X closedir(dirp); X dirsize = ceil_mod(dirsize, dirblksiz); X if (stat(dirname, &statbuf)) { X fprintf(stderr, "%s cannot stat. ignored.¥n", dirname); X return; X } X dirsize_real = (int)statbuf.st_size; X wasted = dirsize_real - dirsize; X X fs_blocksize = statbuf.st_blksize; X if (statfs(dirname, &statfsbuf)) { X fprintf(stderr, "%s cannot statfs. ignored.¥n", dirname); X return; X } X fs_fragsize = (int)statfsbuf.f_bsize; X fs_dirsize_real = fssize(dirsize_real, fs_blocksize, fs_fragsize); X fs_dirsize = fssize(dirsize, fs_blocksize, fs_fragsize); X fs_wasted = fs_dirsize_real - fs_dirsize; X X printf("%8d%8d%8d%8d %s¥n", X dirsize_real, dirsize, wasted, fs_wasted, X dirname); X total_wasted += wasted; X total_fs_wasted += fs_wasted; } X /* X dent_minsize: X return the minimum amount of space in directory file required to represent X the specified directory entry. */ int dent_minsize(entp) DIRENT *entp; { X return dent_minsize_namelen(entp->d_namlen); } X /* X fssize: X return the amount of space required to store a file of specified size X in the filesystem of specified block/fragment size. */ int fssize(filesize, blocksize, fragmentsize) int filesize; int blocksize, fragmentsize; { X if (filesize > blocksize * NDADDR) { /* if using indirect block */ X return ceil_mod(filesize, blocksize); X } else { X return ceil_mod(filesize, fragmentsize); X } } X /* malloc() with error check */ char *emalloc(size) unsigned int size; { X char *malloc(); X char *memregion; X X if ((memregion = malloc(size)) == (char *) NULL) { X fprintf(stderr, "%s: cannot allocate memory.¥n"); X exit(4); X } X return memregion; } X int ceil_mod(i, mod) int i, mod; { X return ((i + mod - 1) / mod) * mod; } SHAR_EOF chmod 0444 dirwaste.c || echo 'restore of dirwaste.c failed' Wc_c="`wc -c < 'dirwaste.c'`" test 5103 -eq "$Wc_c" || echo 'dirwaste.c: original size 5103, current size' "$Wc_c" fi # ============= statistics ============== if test -f 'statistics' -a X"$1" != X"-c"; then echo 'x - skipping statistics (File already exists)' else echo 'x - extracting statistics (Text)' sed 's/^X//' << 'SHAR_EOF' > 'statistics' && 0 0 79816 2 113664 30449 3 564224 88513 4 473088 69418 5 475648 57016 6 419328 26373 7 486912 30084 8 679936 62882 9 839680 83877 10 797696 82474 11 777216 79417 12 643584 45558 13 596480 44537 14 672256 50336 15 841728 82078 16 1021440 102692 17 1112576 113045 18 1069056 104282 19 916992 77665 20 785408 56302 21 762368 47643 23 706560 25910 24 1041408 77621 25 961024 68346 26 822272 43254 27 763392 34216 28 844800 40823 29 1046528 66176 30 1174528 85986 31 1156096 77813 32 1101312 62757 33 961024 38918 34 872960 20546 35 981504 39220 36 1143808 64104 37 1257472 76894 38 1268736 81696 39 1203712 73454 40 1027584 43895 41 927744 26668 42 1015808 30537 43 1212416 59244 44 1335808 76562 45 1341952 79575 46 1297920 77495 47 1143296 46914 48 1077248 35965 49 1182208 47872 50 1392640 77866 51 1542656 96651 52 1678336 101601 53 1610752 86413 54 1420288 61956 55 1282560 33296 56 1246720 34097 57 1530368 57400 58 1526784 65679 59 1501696 65362 60 1447936 62784 61 1240064 29228 62 1245696 28314 63 1276416 28401 64 1415168 47600 65 1508864 58047 66 1512960 62660 67 1392128 45014 68 1272320 24556 69 1189888 6518 70 1329664 20951 71 1447424 42472 72 1513984 52621 73 1509376 55121 74 1505792 58309 75 1624576 73897 76 1299456 15379 77 1334784 28508 78 1489920 50555 79 1452032 38696 80 1609728 58618 81 1589760 48038 82 1410048 24579 83 1362432 12433 84 1450496 25717 85 1646592 55281 86 1749504 71671 87 1726976 68708 88 1653760 58347 89 1476096 30166 90 1364992 8589 91 1452032 21141 92 1657344 52143 93 1790464 67808 94 1777664 73139 95 1721344 67709 96 1577472 40103 97 1492480 19045 98 1524224 22133 99 1728000 48003 100 1781248 53159 101 1851904 61459 102 1746944 42931 103 1629184 25614 104 1502208 5943 105 1534976 5987 106 1961472 30906 107 1716736 32352 108 1687040 25322 109 1622528 14031 110 1980416 67857 111 1765376 24225 112 1650688 5985 113 1742848 19095 114 2025472 60890 115 2140672 79044 116 1981440 55530 117 1818112 33030 118 1601536 5892 119 1586176 5996 120 1801216 32184 121 1905664 41936 122 1841152 23944 123 1769472 6448 124 1817088 14238 125 1806336 5918 126 1886720 21604 127 2151424 63088 128 2389504 90032 129 2017792 40710 130 1875968 21559 131 1774592 5949 132 1778176 5462 133 1818624 5922 134 2012160 29606 135 2042880 26247 136 2043392 23699 137 2061824 28032 138 1931776 13893 139 2032128 32380 140 2252288 59833 141 2438144 79328 142 2633728 104821 143 2484736 72259 144 2188288 39635 145 1965568 5924 146 1990144 5991 147 2059264 5443 148 2067456 5485 149 2334208 42183 150 2460672 54779 151 2242048 33853 152 2067456 5751 153 2226688 10878 154 2302464 31493 155 2487296 57830 156 2697216 87142 157 2640384 71361 158 2465792 45969 159 2570240 43864 160 2520576 35810 161 2266112 20696 162 2426880 51192 163 2552320 69275 164 2594304 77323 165 2241024 17329 166 2533376 57165 167 2292224 21946 168 2321920 19052 169 2610688 66290 170 2708992 75941 171 2671104 70739 172 2447872 29191 173 2370048 17743 174 2344960 24136 175 2409984 42286 176 2580992 70302 177 2724352 66229 178 2597888 39931 179 2477568 14767 180 2483712 27368 181 2394624 24908 182 2355200 24530 183 2496000 34047 184 2710528 62042 185 2613760 46053 186 2411008 23649 187 2250240 7905 188 2302976 11403 189 2401792 21081 190 2715136 66422 191 2798080 82258 192 2684416 58496 193 2596864 37521 194 2471424 19296 195 2741760 67651 196 2913280 73289 197 3234816 121606 198 3171328 108255 199 2895872 70353 200 2746880 53845 201 2684928 38787 202 2691584 42964 203 2465792 10474 204 2465792 5670 205 2589184 20501 206 2857984 54518 207 2649088 5003 208 2725888 8430 209 2895872 37110 210 2746880 24489 211 2680320 7784 212 2923008 60586 213 2644992 20464 214 2953728 66056 215 2742272 5889 216 2636800 5137 217 3094016 74946 218 3229696 98030 219 3120640 83146 220 3120640 83913 221 2913792 47901 222 2958848 52034 223 3092992 73396 224 3426304 119874 225 3668480 162959 226 3803136 183351 227 3551744 143433 228 3470336 135997 229 3100672 79743 230 3001344 61308 231 3062784 57695 232 3145216 70240 233 3152384 66833 234 2990592 35306 235 2896896 34558 236 3354624 64572 237 2875904 25856 238 3058176 48598 239 3054080 36207 240 3175424 55732 241 2948096 18430 242 2820608 5981 243 2864640 5986 244 2902016 5994 245 3253760 52462 246 3381760 75671 247 3381760 75007 248 3100672 18891 249 2969600 5982 250 2954240 5971 251 2900480 5987 252 2884096 5959 253 3174400 44527 254 3320320 57014 255 3148288 26672 256 3039744 5994 257 3277312 22260 258 2963968 10197 259 3102208 10241 SHAR_EOF chmod 0644 statistics || echo 'restore of statistics failed' Wc_c="`wc -c < 'statistics'`" test 4485 -eq "$Wc_c" || echo 'statistics: original size 4485, current size' "$Wc_c" fi exit 0