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

Comparing libeio/eio.c (file contents):
Revision 1.30 by root, Wed Jun 3 12:24:49 2009 UTC vs.
Revision 1.41 by root, Sun Jun 14 20:36:59 2009 UTC

1/* 1/*
2 * libeio implementation 2 * libeio implementation
3 * 3 *
4 * Copyright (c) 2007,2008 Marc Alexander Lehmann <libeio@schmorp.de> 4 * Copyright (c) 2007,2008,2009 Marc Alexander Lehmann <libeio@schmorp.de>
5 * All rights reserved. 5 * All rights reserved.
6 * 6 *
7 * Redistribution and use in source and binary forms, with or without modifica- 7 * Redistribution and use in source and binary forms, with or without modifica-
8 * tion, are permitted provided that the following conditions are met: 8 * tion, are permitted provided that the following conditions are met:
9 * 9 *
68#endif 68#endif
69 69
70#ifdef _WIN32 70#ifdef _WIN32
71 71
72 /*doh*/ 72 /*doh*/
73
74#else 73#else
75 74
76# include "config.h" 75# include "config.h"
77# include <sys/time.h> 76# include <sys/time.h>
78# include <sys/select.h> 77# include <sys/select.h>
78# include <sys/mman.h>
79# include <unistd.h> 79# include <unistd.h>
80# include <utime.h> 80# include <utime.h>
81# include <signal.h> 81# include <signal.h>
82# include <dirent.h> 82# include <dirent.h>
83
84/* POSIX_SOURCE is useless on bsd's, and XOPEN_SOURCE is unreliable there, too */
85# if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__)
86# define _DIRENT_HAVE_D_TYPE /* sigh */
87# define D_INO(de) (de)->d_fileno
88# define D_NAMLEN(de) (de)->d_namlen
89# elif defined(__linux) || defined(d_ino) || _XOPEN_SOURCE >= 600
90# define D_INO(de) (de)->d_ino
91# endif
92
93#ifdef _D_EXACT_NAMLEN
94# undef D_NAMLEN
95# define D_NAMLEN(de) _D_EXACT_NAMLEN (de)
96#endif
97
98# ifdef _DIRENT_HAVE_D_TYPE
99# define D_TYPE(de) (de)->d_type
100# endif
83 101
84# ifndef EIO_STRUCT_DIRENT 102# ifndef EIO_STRUCT_DIRENT
85# define EIO_STRUCT_DIRENT struct dirent 103# define EIO_STRUCT_DIRENT struct dirent
86# endif 104# endif
87 105
100# else 118# else
101# error sendfile support requested but not available 119# error sendfile support requested but not available
102# endif 120# endif
103#endif 121#endif
104 122
123#ifndef D_TYPE
124# define D_TYPE(de) 0
125#endif
126#ifndef D_INO
127# define D_INO(de) 0
128#endif
129#ifndef D_NAMLEN
130# define D_NAMLEN(de) strlen ((de)->d_name)
131#endif
132
105/* number of seconds after which an idle threads exit */ 133/* number of seconds after which an idle threads exit */
106#define IDLE_TIMEOUT 10 134#define IDLE_TIMEOUT 10
107 135
108/* used for struct dirent, AIX doesn't provide it */ 136/* used for struct dirent, AIX doesn't provide it */
109#ifndef NAME_MAX 137#ifndef NAME_MAX
159 if (wrk->dirp) \ 187 if (wrk->dirp) \
160 { \ 188 { \
161 closedir (wrk->dirp); \ 189 closedir (wrk->dirp); \
162 wrk->dirp = 0; \ 190 wrk->dirp = 0; \
163 } 191 }
192
164#define ETP_WORKER_COMMON \ 193#define ETP_WORKER_COMMON \
165 void *dbuf; \ 194 void *dbuf; \
166 DIR *dirp; 195 DIR *dirp;
167 196
168/*****************************************************************************/ 197/*****************************************************************************/
961 } 990 }
962 991
963 return res; 992 return res;
964} 993}
965 994
995static signed char
996eio_dent_cmp (const eio_dirent *a, const eio_dirent *b)
997{
998 return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */
999 : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0;
1000}
1001
1002#define EIO_DENT_CMP(i,op,j) eio_dent_cmp (&i, &j) op 0
1003#define EIO_DENT_NUM_SCORES 9
1004
1005#define EIO_QSORT_CUTOFF 30 /* quite high, but performs well on many filesystems */
1006#define EIO_QSORT_SKIP 60 /* when to skip qsort completely */
1007
1008static void
1009eio_dent_sort (eio_dirent *dents, int size)
1010{
1011 if (size <= 1)
1012 return; /* our insertion sort relies on size > 0 */
1013
1014 if (size > EIO_QSORT_SKIP) /* skip quicksort for small directories */
1015 {
1016 /* first, use quicksort */
1017 /* should be good for 2**31 entries */
1018 int i;
1019 struct rng { eio_dirent *l, *r; } rng [32];
1020
1021 i = 0;
1022 rng[0].l = dents;
1023 rng[0].r = dents + size;
1024
1025 while (expect_true (i >= 0))
1026 {
1027 eio_dirent *L = rng [i].l;
1028 eio_dirent *R = rng [i].r - 1;
1029
1030 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1031 {
1032 eio_dirent *mid = &dents [((L - dents) + (R - dents)) >> 1];
1033 eio_dirent piv = *mid; *mid = *L; *L = piv;
1034
1035 while (L < R)
1036 {
1037 while (EIO_DENT_CMP (*R, >=, piv) && L < R)
1038 --R;
1039
1040 if (L < R)
1041 *L++ = *R;
1042
1043 while (EIO_DENT_CMP (*L, <=, piv) && L < R)
1044 ++L;
1045
1046 if (L < R)
1047 *R-- = *L;
1048 }
1049
1050 *L = piv;
1051
1052 ++i;
1053 rng [i].l = L + 1;
1054 rng [i].r = rng [i - 1].r;
1055 rng [i - 1].r = L;
1056
1057 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1058 {
1059 struct rng t;
1060
1061 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1062 }
1063 }
1064 else
1065 --i;
1066 }
1067 }
1068
1069 /* use an insertion sort after qsort, or for small arrays */
1070 /* first move the smallest element to the front, to act as a sentinel */
1071 {
1072 int i;
1073 eio_dirent *min = dents;
1074
1075 for (i = size > EIO_QSORT_SKIP ? EIO_QSORT_CUTOFF + 1 : size; --i; )
1076 if (EIO_DENT_CMP (dents [i], <, *min))
1077 min = &dents [i];
1078
1079 /* swap elements 0 and j (minimum) */
1080 {
1081 eio_dirent tmp = *dents; *dents = *min; *min = tmp;
1082 }
1083 }
1084
1085 {
1086 /* then do standard insertion sort */
1087 eio_dirent *i, *j;
1088
1089 for (i = dents + 1; i < dents + size; ++i)
1090 {
1091 eio_dirent value = *i;
1092
1093 for (j = i - 1; EIO_DENT_CMP (*j, >, value); --j)
1094 j [1] = j [0];
1095
1096 j [1] = value;
1097 }
1098 }
1099}
1100
966/* read a full directory */ 1101/* read a full directory */
967static void 1102static void
968eio__scandir (eio_req *req, etp_worker *self) 1103eio__scandir (eio_req *req, etp_worker *self)
969{ 1104{
970 DIR *dirp; 1105 DIR *dirp;
971 EIO_STRUCT_DIRENT *entp; 1106 EIO_STRUCT_DIRENT *entp;
972 char *name, *names; 1107 char *name, *names;
973 int memlen = 4096; 1108 int namesalloc = 4096;
974 int memofs = 0; 1109 int namesoffs = 0;
1110 int flags = req->int1;
1111 eio_dirent *dents = 0;
1112 int dentalloc = 128;
975 int res = 0; 1113 int dentoffs = 0;
1114
1115 req->result = -1;
1116
1117 if (!(flags & EIO_READDIR_DENTS))
1118 flags &= ~(EIO_READDIR_DIRS_FIRST | EIO_READDIR_STAT_ORDER);
976 1119
977 X_LOCK (wrklock); 1120 X_LOCK (wrklock);
978 /* the corresponding closedir is in ETP_WORKER_CLEAR */ 1121 /* the corresponding closedir is in ETP_WORKER_CLEAR */
979 self->dirp = dirp = opendir (req->ptr1); 1122 self->dirp = dirp = opendir (req->ptr1);
980 req->flags |= EIO_FLAG_PTR2_FREE; 1123 req->flags |= EIO_FLAG_PTR1_FREE | EIO_FLAG_PTR2_FREE;
981 req->ptr2 = names = malloc (memlen); 1124 req->ptr1 = names = malloc (namesalloc);
1125 req->ptr2 = dents = flags ? malloc (dentalloc * sizeof (eio_dirent)) : 0;
982 X_UNLOCK (wrklock); 1126 X_UNLOCK (wrklock);
983 1127
984 if (dirp && names) 1128 if (dirp && names && (!flags || dents))
985 for (;;) 1129 for (;;)
986 { 1130 {
987 errno = 0; 1131 errno = 0;
988 entp = readdir (dirp); 1132 entp = readdir (dirp);
989 1133
990 if (!entp) 1134 if (!entp)
1135 {
1136 if (errno)
1137 break;
1138
1139 /* sort etc. */
1140 req->int1 = flags;
1141 req->result = dentoffs;
1142
1143 if (dents)
1144 {
1145 eio_dirent *ent = dents + dentoffs;
1146
1147 while (ent > dents)
1148 (--ent)->name = names + (size_t)ent->name;
1149 }
1150
1151 if (flags & EIO_READDIR_STAT_ORDER
1152 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1153 eio_dent_sort (dents, dentoffs); /* score depends of DIRS_FIRST */
1154 else if (flags & EIO_READDIR_DIRS_FIRST)
1155 {
1156 /* in this case, all is known, and we just put dirs first and sort them */
1157 eio_dirent *ent = dents + dentoffs;
1158 eio_dirent *dir = dents;
1159
1160 /* now move dirs to the front, and non-dirs to the back */
1161 /* by walking from both sides and swapping if necessary */
1162 while (ent > dir)
1163 {
1164 if (dir->type == DT_DIR)
1165 {
1166 dir->score = 0;
1167 ++dir;
1168 }
1169 else
1170 {
1171 --ent;
1172
1173 if (ent->type == DT_DIR)
1174 {
1175 eio_dirent tmp = *dir;
1176 *dir = *ent;
1177 *ent = tmp;
1178
1179 dir->score = 0;
1180 ++dir;
1181 }
1182 }
1183 }
1184
1185 /* now sort the dirs only */
1186 eio_dent_sort (dents, dir - dents);
1187 }
1188
1189 /* only provide the names array unless DENTS is specified */
1190 if (!(flags & EIO_READDIR_DENTS))
1191 {
1192 X_LOCK (wrklock);
1193 assert (!dents);
1194 req->ptr1 = 0;
1195 req->ptr2 = names;
1196 X_UNLOCK (wrklock);
1197 }
1198
991 break; 1199 break;
1200 }
992 1201
1202 /* now add the entry to our list(s) */
993 name = entp->d_name; 1203 name = entp->d_name;
994 1204
1205 /* skip . and .. entries */
995 if (name [0] != '.' || (name [1] && (name [1] != '.' || name [2]))) 1206 if (name [0] != '.' || (name [1] && (name [1] != '.' || name [2])))
996 { 1207 {
997 int len = strlen (name) + 1; 1208 int len = D_NAMLEN (entp) + 1;
998 1209
999 res++; 1210 while (expect_false (namesoffs + len > namesalloc))
1000
1001 while (memofs + len > memlen)
1002 { 1211 {
1003 memlen *= 2; 1212 namesalloc *= 2;
1004 X_LOCK (wrklock); 1213 X_LOCK (wrklock);
1005 req->ptr2 = names = realloc (names, memlen); 1214 req->ptr1 = names = realloc (names, namesalloc);
1006 X_UNLOCK (wrklock); 1215 X_UNLOCK (wrklock);
1007 1216
1008 if (!names) 1217 if (!names)
1009 break; 1218 break;
1010 } 1219 }
1011 1220
1012 memcpy (names + memofs, name, len); 1221 memcpy (names + namesoffs, name, len);
1222
1223 if (dents)
1224 {
1225 struct eio_dirent *ent;
1226
1227 if (expect_false (dentoffs == dentalloc))
1228 {
1229 dentalloc *= 2;
1230 X_LOCK (wrklock);
1231 req->ptr2 = dents = realloc (dents, dentalloc * sizeof (eio_dirent));
1232 X_UNLOCK (wrklock);
1233
1234 if (!dents)
1235 break;
1236 }
1237
1238 ent = dents + dentoffs;
1239
1240 ent->name = (char *)(size_t)namesoffs; /* rather dirtily we store the offset in the pointer */
1241 ent->namelen = len - 1;
1242 ent->inode = D_INO (entp) ? D_INO (entp) : dentoffs;
1243
1244 switch (D_TYPE (entp))
1245 {
1246 default:
1247 ent->type = EIO_DT_UNKNOWN;
1248 flags |= EIO_READDIR_FOUND_UNKNOWN;
1249 break;
1250
1251 #ifdef DT_FIFO
1252 case DT_FIFO: ent->type = EIO_DT_FIFO; break;
1253 #endif
1254 #ifdef DT_CHR
1255 case DT_CHR: ent->type = EIO_DT_CHR; break;
1256 #endif
1257 #ifdef DT_MPC
1258 case DT_MPC: ent->type = EIO_DT_MPC; break;
1259 #endif
1260 #ifdef DT_DIR
1261 case DT_DIR: ent->type = EIO_DT_DIR; break;
1262 #endif
1263 #ifdef DT_NAM
1264 case DT_NAM: ent->type = EIO_DT_NAM; break;
1265 #endif
1266 #ifdef DT_BLK
1267 case DT_BLK: ent->type = EIO_DT_BLK; break;
1268 #endif
1269 #ifdef DT_MPB
1270 case DT_MPB: ent->type = EIO_DT_MPB; break;
1271 #endif
1272 #ifdef DT_REG
1273 case DT_REG: ent->type = EIO_DT_REG; break;
1274 #endif
1275 #ifdef DT_NWK
1276 case DT_NWK: ent->type = EIO_DT_NWK; break;
1277 #endif
1278 #ifdef DT_CMP
1279 case DT_CMP: ent->type = EIO_DT_CMP; break;
1280 #endif
1281 #ifdef DT_LNK
1282 case DT_LNK: ent->type = EIO_DT_LNK; break;
1283 #endif
1284 #ifdef DT_SOCK
1285 case DT_SOCK: ent->type = EIO_DT_SOCK; break;
1286 #endif
1287 #ifdef DT_DOOR
1288 case DT_DOOR: ent->type = EIO_DT_DOOR; break;
1289 #endif
1290 #ifdef DT_WHT
1291 case DT_WHT: ent->type = EIO_DT_WHT; break;
1292 #endif
1293 }
1294
1295 ent->score = 0;
1296
1297 if (flags & EIO_READDIR_DIRS_FIRST)
1298 {
1299 if (ent->type == EIO_DT_UNKNOWN)
1300 {
1301 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
1302 ent->score = 7;
1303 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
1304 ent->score = len <= 2 ? len + 4 : len <= 4 ? 3 : len <= 7 ? 2 : 1; /* shorter == more likely dir, but avoid too many classes */
1305 }
1306 else if (ent->type == EIO_DT_DIR)
1307 ent->score = 8;
1308 }
1309 }
1310
1013 memofs += len; 1311 namesoffs += len;
1312 ++dentoffs;
1313 }
1314
1315 if (EIO_CANCELLED (req))
1316 {
1317 errno = ECANCELED;
1318 break;
1014 } 1319 }
1015 } 1320 }
1016
1017 if (errno)
1018 res = -1;
1019
1020 req->result = res;
1021} 1321}
1022 1322
1023#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO) 1323#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO)
1024# undef msync 1324# undef msync
1025# define msync(a,b,c) ((errno = ENOSYS), -1) 1325# define msync(a,b,c) ((errno = ENOSYS), -1)
1445eio_req *eio_rmdir (const char *path, int pri, eio_cb cb, void *data) 1745eio_req *eio_rmdir (const char *path, int pri, eio_cb cb, void *data)
1446{ 1746{
1447 return eio__1path (EIO_RMDIR, path, pri, cb, data); 1747 return eio__1path (EIO_RMDIR, path, pri, cb, data);
1448} 1748}
1449 1749
1450eio_req *eio_readdir (const char *path, int pri, eio_cb cb, void *data) 1750eio_req *eio_readdir (const char *path, int flags, int pri, eio_cb cb, void *data)
1451{ 1751{
1452 return eio__1path (EIO_READDIR, path, pri, cb, data); 1752 REQ (EIO_READDIR); PATH; req->int1 = flags; SEND;
1453} 1753}
1454 1754
1455eio_req *eio_mknod (const char *path, mode_t mode, dev_t dev, int pri, eio_cb cb, void *data) 1755eio_req *eio_mknod (const char *path, mode_t mode, dev_t dev, int pri, eio_cb cb, void *data)
1456{ 1756{
1457 REQ (EIO_MKNOD); PATH; req->int2 = (long)mode; req->int3 = (long)dev; SEND; 1757 REQ (EIO_MKNOD); PATH; req->int2 = (long)mode; req->int3 = (long)dev; SEND;
1546/* misc garbage */ 1846/* misc garbage */
1547 1847
1548ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1848ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1549{ 1849{
1550 etp_worker wrk; 1850 etp_worker wrk;
1851 ssize_t ret;
1551 1852
1552 wrk.dbuf = 0; 1853 wrk.dbuf = 0;
1553 1854
1554 eio__sendfile (ofd, ifd, offset, count, &wrk); 1855 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1555 1856
1556 if (wrk.dbuf) 1857 if (wrk.dbuf)
1557 free (wrk.dbuf); 1858 free (wrk.dbuf);
1558}
1559 1859
1860 return ret;
1861}
1862

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines