ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/cvsroot/libeio/eio.c
(Generate patch)

Comparing cvsroot/libeio/eio.c (file contents):
Revision 1.32 by root, Sat Jun 6 18:06:55 2009 UTC vs.
Revision 1.37 by root, Fri Jun 12 16:48:08 2009 UTC

… …
73#else 73#else
74 74
75# include "config.h" 75# include "config.h"
76# include <sys/time.h> 76# include <sys/time.h>
77# include <sys/select.h> 77# include <sys/select.h>
78# include <sys/mman.h>
78# include <unistd.h> 79# include <unistd.h>
79# include <utime.h> 80# include <utime.h>
80# include <signal.h> 81# include <signal.h>
81# include <dirent.h> 82# include <dirent.h>
82 83
83/* POSIX_SOURCE is useless on bsd's, and XOPEN_SOURCE is unreliable there, too */ 84/* POSIX_SOURCE is useless on bsd's, and XOPEN_SOURCE is unreliable there, too */
84# if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) 85# if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__)
86# define _DIRENT_HAVE_D_TYPE /* sigh */
85# define D_INO(de) (de)->d_fileno 87# define D_INO(de) (de)->d_fileno
86# define _DIRENT_HAVE_D_TYPE /* sigh */ 88# define D_NAMLEN(de) (de)->d_namlen
87# elif defined(__linux) || defined(d_ino) || _XOPEN_SOURCE >= 600 89# elif defined(__linux) || defined(d_ino) || _XOPEN_SOURCE >= 600
88# define D_INO(de) (de)->d_ino 90# define D_INO(de) (de)->d_ino
89# endif 91# endif
92
93#ifdef _D_EXACT_NAMLEN
94# undef D_NAMLEN
95# define D_NAMLEN(de) _D_EXACT_NAMLEN (de)
96#endif
90 97
91# ifdef _DIRENT_HAVE_D_TYPE 98# ifdef _DIRENT_HAVE_D_TYPE
92# define D_TYPE(de) (de)->d_type 99# define D_TYPE(de) (de)->d_type
93# endif 100# endif
94 101
… …
114#endif 121#endif
115 122
116#ifndef D_TYPE 123#ifndef D_TYPE
117# define D_TYPE(de) 0 124# define D_TYPE(de) 0
118#endif 125#endif
119
120#ifndef D_INO 126#ifndef D_INO
121# define D_INO(de) 0 127# define D_INO(de) 0
128#endif
129#ifndef D_NAMLEN
130# define D_NAMLEN(de) strlen ((de)->d_name)
122#endif 131#endif
123 132
124/* number of seconds after which an idle threads exit */ 133/* number of seconds after which an idle threads exit */
125#define IDLE_TIMEOUT 10 134#define IDLE_TIMEOUT 10
126 135
… …
981 } 990 }
982 991
983 return res; 992 return res;
984} 993}
985 994
986static int 995static signed char
987eio_dent_cmp (const void *a_, const void *b_) 996eio_dent_cmp (const eio_dirent *a, const eio_dirent *b)
988{ 997{
989 const eio_dirent *a = (const eio_dirent *)a_; 998 return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */
990 const eio_dirent *b = (const eio_dirent *)b_;
991
992 return (int)b->score - (int)a->score ? (int)b->score - (int)a->score
993 : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0; /* int might be < ino_t */ 999 : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0;
1000}
1001
1002#define EIO_QSORT_CUTOFF 20 /* quite high, but performs well on many filesystems */
1003
1004static void
1005eio_dent_sort (eio_dirent *dents, int size)
1006{
1007 /* should be good for 2**31 entries */
1008 struct rng { int l, r; } rng [32];
1009 int i, j;
1010
1011 i = 0;
1012 rng[0].l = 0;
1013 rng[0].r = size;
1014
1015 while (expect_true (i >= 0))
1016 {
1017 int L = rng [i].l;
1018 int R = rng [i].r - 1;
1019
1020 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1021 {
1022 eio_dirent piv = dents [L];
1023
1024 while (L < R)
1025 {
1026 while (eio_dent_cmp (&dents [R], &piv) >= 0 && L < R)
1027 --R;
1028
1029 if (L < R)
1030 dents [L++] = dents [R];
1031
1032 while (eio_dent_cmp (&dents [L], &piv) <= 0 && L < R)
1033 ++L;
1034
1035 if (L < R)
1036 dents [R--] = dents [L];
1037 }
1038
1039 dents [L] = piv;
1040
1041 ++i;
1042 rng [i].l = L + 1;
1043 rng [i].r = rng [i - 1].r;
1044 rng [i - 1].r = L;
1045
1046 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1047 {
1048 struct rng t;
1049
1050 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1051 }
1052 }
1053 else
1054 --i;
1055 }
1056
1057 /* use a simple insertion sort at the end */
1058 for (i = 1; i < size; ++i)
1059 {
1060 eio_dirent value = dents [i];
1061
1062 for (j = i - 1; j >= 0 && eio_dent_cmp (&dents [j], &value) > 0; --j)
1063 dents [j + 1] = dents [j];
1064
1065 dents [j + 1] = value;
1066 }
994} 1067}
995 1068
996/* read a full directory */ 1069/* read a full directory */
997static void 1070static void
998eio__scandir (eio_req *req, etp_worker *self) 1071eio__scandir (eio_req *req, etp_worker *self)
999{ 1072{
1000 DIR *dirp; 1073 DIR *dirp;
1001 EIO_STRUCT_DIRENT *entp; 1074 EIO_STRUCT_DIRENT *entp;
1002 unsigned char *name, *names; 1075 char *name, *names;
1003 int namesalloc = 4096; 1076 int namesalloc = 4096;
1004 int namesoffs = 0; 1077 int namesoffs = 0;
1005 int flags = req->int1; 1078 int flags = req->int1;
1006 eio_dirent *dents = 0; 1079 eio_dirent *dents = 0;
1007 int dentalloc = 128; 1080 int dentalloc = 128;
… …
1043 (--ent)->name = names + (size_t)ent->name; 1116 (--ent)->name = names + (size_t)ent->name;
1044 } 1117 }
1045 1118
1046 if (flags & EIO_READDIR_STAT_ORDER 1119 if (flags & EIO_READDIR_STAT_ORDER
1047 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN))) 1120 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1048 { 1121 eio_dent_sort (dents, dentoffs); /* score depends of DIRS_FIRST */
1049 /* pray your qsort doesn't use quicksort */
1050 qsort (dents, dentoffs, sizeof (*dents), eio_dent_cmp); /* score depends of DIRS_FIRST */
1051 }
1052 else if (flags & EIO_READDIR_DIRS_FIRST) 1122 else if (flags & EIO_READDIR_DIRS_FIRST)
1053 { 1123 {
1054 /* in this case, all is known, and we just put dirs first and sort them */ 1124 /* in this case, all is known, and we just put dirs first and sort them */
1055 eio_dirent *ent = dents + dentoffs; 1125 eio_dirent *ent = dents + dentoffs;
1056 eio_dirent *dir = dents; 1126 eio_dirent *dir = dents;
1057 1127
1128 /* now move dirs to the front, and non-dirs to the back */
1129 /* by walking from both sides and swapping if necessary */
1058 while (ent > dir) 1130 while (ent > dir)
1059 { 1131 {
1060 if (dir->type == DT_DIR) 1132 if (dir->type == DT_DIR)
1061 ++dir; 1133 ++dir;
1062 else 1134 else
… …
1073 } 1145 }
1074 } 1146 }
1075 } 1147 }
1076 1148
1077 /* now sort the dirs only */ 1149 /* now sort the dirs only */
1078 qsort (dents, dir - dents, sizeof (*dents), eio_dent_cmp); 1150 eio_dent_sort (dents, dir - dents);
1079 } 1151 }
1080 1152
1081 /* only provide the names array unless DENTS is specified */ 1153 /* only provide the names array unless DENTS is specified */
1082 if (!(flags & EIO_READDIR_DENTS)) 1154 if (!(flags & EIO_READDIR_DENTS))
1083 { 1155 {
… …
1095 name = entp->d_name; 1167 name = entp->d_name;
1096 1168
1097 /* skip . and .. entries */ 1169 /* skip . and .. entries */
1098 if (name [0] != '.' || (name [1] && (name [1] != '.' || name [2]))) 1170 if (name [0] != '.' || (name [1] && (name [1] != '.' || name [2])))
1099 { 1171 {
1100 int len = strlen (name) + 1; 1172 int len = D_NAMLEN (entp) + 1;
1101 1173
1102 while (expect_false (namesoffs + len > namesalloc)) 1174 while (expect_false (namesoffs + len > namesalloc))
1103 { 1175 {
1104 namesalloc *= 2; 1176 namesalloc *= 2;
1105 X_LOCK (wrklock); 1177 X_LOCK (wrklock);
… …
1144 case DT_FIFO: ent->type = EIO_DT_FIFO; break; 1216 case DT_FIFO: ent->type = EIO_DT_FIFO; break;
1145 #endif 1217 #endif
1146 #ifdef DT_CHR 1218 #ifdef DT_CHR
1147 case DT_CHR: ent->type = EIO_DT_CHR; break; 1219 case DT_CHR: ent->type = EIO_DT_CHR; break;
1148 #endif 1220 #endif
1221 #ifdef DT_MPC
1222 case DT_MPC: ent->type = EIO_DT_MPC; break;
1223 #endif
1149 #ifdef DT_DIR 1224 #ifdef DT_DIR
1150 case DT_DIR: ent->type = EIO_DT_DIR; break; 1225 case DT_DIR: ent->type = EIO_DT_DIR; break;
1226 #endif
1227 #ifdef DT_NAM
1228 case DT_NAM: ent->type = EIO_DT_NAM; break;
1151 #endif 1229 #endif
1152 #ifdef DT_BLK 1230 #ifdef DT_BLK
1153 case DT_BLK: ent->type = EIO_DT_BLK; break; 1231 case DT_BLK: ent->type = EIO_DT_BLK; break;
1154 #endif 1232 #endif
1233 #ifdef DT_MPB
1234 case DT_MPB: ent->type = EIO_DT_MPB; break;
1235 #endif
1155 #ifdef DT_REG 1236 #ifdef DT_REG
1156 case DT_REG: ent->type = EIO_DT_REG; break; 1237 case DT_REG: ent->type = EIO_DT_REG; break;
1238 #endif
1239 #ifdef DT_NWK
1240 case DT_NWK: ent->type = EIO_DT_NWK; break;
1241 #endif
1242 #ifdef DT_CMP
1243 case DT_CMP: ent->type = EIO_DT_CMP; break;
1157 #endif 1244 #endif
1158 #ifdef DT_LNK 1245 #ifdef DT_LNK
1159 case DT_LNK: ent->type = EIO_DT_LNK; break; 1246 case DT_LNK: ent->type = EIO_DT_LNK; break;
1160 #endif 1247 #endif
1161 #ifdef DT_SOCK 1248 #ifdef DT_SOCK
1162 case DT_SOCK: ent->type = EIO_DT_SOCK; break; 1249 case DT_SOCK: ent->type = EIO_DT_SOCK; break;
1163 #endif 1250 #endif
1251 #ifdef DT_DOOR
1252 case DT_DOOR: ent->type = EIO_DT_DOOR; break;
1253 #endif
1164 #ifdef DT_WHT 1254 #ifdef DT_WHT
1165 case DT_WHT: ent->type = EIO_DT_WHT; break; 1255 case DT_WHT: ent->type = EIO_DT_WHT; break;
1166 #endif 1256 #endif
1167 } 1257 }
1168 1258
… …
1173 if (ent->type == EIO_DT_UNKNOWN) 1263 if (ent->type == EIO_DT_UNKNOWN)
1174 { 1264 {
1175 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */ 1265 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
1176 ent->score = 98; 1266 ent->score = 98;
1177 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */ 1267 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
1178 ent->score = len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */ 1268 ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */
1179 } 1269 }
1180 else if (ent->type == DT_DIR) 1270 else if (ent->type == EIO_DT_DIR)
1181 ent->score = 100; 1271 ent->score = 100;
1182 } 1272 }
1183 } 1273 }
1184 1274
1185 namesoffs += len; 1275 namesoffs += len;
1186 ++dentoffs; 1276 ++dentoffs;
1187 } 1277 }
1278
1279 if (EIO_CANCELLED (req))
1280 {
1281 errno = ECANCELED;
1282 break;
1283 }
1188 } 1284 }
1189 else
1190 req->result = -1;
1191} 1285}
1192 1286
1193#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO) 1287#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO)
1194# undef msync 1288# undef msync
1195# define msync(a,b,c) ((errno = ENOSYS), -1) 1289# define msync(a,b,c) ((errno = ENOSYS), -1)
… …
1716/* misc garbage */ 1810/* misc garbage */
1717 1811
1718ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1812ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1719{ 1813{
1720 etp_worker wrk; 1814 etp_worker wrk;
1815 ssize_t ret;
1721 1816
1722 wrk.dbuf = 0; 1817 wrk.dbuf = 0;
1723 1818
1724 eio__sendfile (ofd, ifd, offset, count, &wrk); 1819 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1725 1820
1726 if (wrk.dbuf) 1821 if (wrk.dbuf)
1727 free (wrk.dbuf); 1822 free (wrk.dbuf);
1728}
1729 1823
1824 return ret;
1825}
1826

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines