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.39 by root, Sat Jun 13 03:59:04 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
1004#define EIO_QSORT_CUTOFF 30 /* quite high, but performs well on many filesystems */
1005#define EIO_QSORT_SKIP 60 /* when to skip qsort completely */
1006
1007static void
1008eio_dent_sort (eio_dirent *dents, int size)
1009{
1010 int i, j;
1011
1012 if (size <= 1)
1013 return; /* our insertion sort relies on size > 0 */
1014
1015 if (size > EIO_QSORT_SKIP) /* skip quicksort for small directories */
1016 {
1017 /* first, use quicksort */
1018 /* should be good for 2**31 entries */
1019 struct rng { int l, r; } rng [32];
1020
1021 i = 0;
1022 rng[0].l = 0;
1023 rng[0].r = size;
1024
1025 while (expect_true (i >= 0))
1026 {
1027 int L = rng [i].l;
1028 int R = rng [i].r - 1;
1029
1030 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1031 {
1032 eio_dirent piv = dents [L];
1033
1034 while (L < R)
1035 {
1036 while (EIO_DENT_CMP (dents [R], >=, piv) && L < R)
1037 --R;
1038
1039 if (L < R)
1040 dents [L++] = dents [R];
1041
1042 while (EIO_DENT_CMP (dents [L], <=, piv) && L < R)
1043 ++L;
1044
1045 if (L < R)
1046 dents [R--] = dents [L];
1047 }
1048
1049 dents [L] = piv;
1050
1051 ++i;
1052 rng [i].l = L + 1;
1053 rng [i].r = rng [i - 1].r;
1054 rng [i - 1].r = L;
1055
1056 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1057 {
1058 struct rng t;
1059
1060 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1061 }
1062 }
1063 else
1064 --i;
1065 }
1066 }
1067
1068 /* use an insertion sort after qsort, or for small arrays */
1069 /* first move the smallest element to the front, to act as a sentinel */
1070 {
1071 int min = 0;
1072
1073 for (i = size > EIO_QSORT_SKIP ? EIO_QSORT_CUTOFF : size; --i; )
1074 if (EIO_DENT_CMP (dents [i], <, dents [min]))
1075 min = i;
1076
1077 /* swap elements 0 and j (minimum) */
1078 {
1079 eio_dirent tmp = dents [0]; dents [0] = dents [min]; dents [min] = tmp;
1080 }
1081 }
1082
1083 /* then do standard insertion sort */
1084 for (i = 1; i < size; ++i)
1085 {
1086 eio_dirent value = dents [i];
1087
1088 for (j = i - 1; EIO_DENT_CMP (dents [j], >, value); --j)
1089 dents [j + 1] = dents [j];
1090
1091 dents [j + 1] = value;
1092 }
1093}
1094
966/* read a full directory */ 1095/* read a full directory */
967static void 1096static void
968eio__scandir (eio_req *req, etp_worker *self) 1097eio__scandir (eio_req *req, etp_worker *self)
969{ 1098{
970 DIR *dirp; 1099 DIR *dirp;
971 EIO_STRUCT_DIRENT *entp; 1100 EIO_STRUCT_DIRENT *entp;
972 char *name, *names; 1101 char *name, *names;
973 int memlen = 4096; 1102 int namesalloc = 4096;
974 int memofs = 0; 1103 int namesoffs = 0;
1104 int flags = req->int1;
1105 eio_dirent *dents = 0;
1106 int dentalloc = 128;
975 int res = 0; 1107 int dentoffs = 0;
1108
1109 req->result = -1;
1110
1111 if (!(flags & EIO_READDIR_DENTS))
1112 flags &= ~(EIO_READDIR_DIRS_FIRST | EIO_READDIR_STAT_ORDER);
976 1113
977 X_LOCK (wrklock); 1114 X_LOCK (wrklock);
978 /* the corresponding closedir is in ETP_WORKER_CLEAR */ 1115 /* the corresponding closedir is in ETP_WORKER_CLEAR */
979 self->dirp = dirp = opendir (req->ptr1); 1116 self->dirp = dirp = opendir (req->ptr1);
980 req->flags |= EIO_FLAG_PTR2_FREE; 1117 req->flags |= EIO_FLAG_PTR1_FREE | EIO_FLAG_PTR2_FREE;
981 req->ptr2 = names = malloc (memlen); 1118 req->ptr1 = names = malloc (namesalloc);
1119 req->ptr2 = dents = flags ? malloc (dentalloc * sizeof (eio_dirent)) : 0;
982 X_UNLOCK (wrklock); 1120 X_UNLOCK (wrklock);
983 1121
984 if (dirp && names) 1122 if (dirp && names && (!flags || dents))
985 for (;;) 1123 for (;;)
986 { 1124 {
987 errno = 0; 1125 errno = 0;
988 entp = readdir (dirp); 1126 entp = readdir (dirp);
989 1127
990 if (!entp) 1128 if (!entp)
1129 {
1130 if (errno)
1131 break;
1132
1133 /* sort etc. */
1134 req->int1 = flags;
1135 req->result = dentoffs;
1136
1137 if (dents)
1138 {
1139 eio_dirent *ent = dents + dentoffs;
1140
1141 while (ent > dents)
1142 (--ent)->name = names + (size_t)ent->name;
1143 }
1144
1145 if (flags & EIO_READDIR_STAT_ORDER
1146 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1147 eio_dent_sort (dents, dentoffs); /* score depends of DIRS_FIRST */
1148 else if (flags & EIO_READDIR_DIRS_FIRST)
1149 {
1150 /* in this case, all is known, and we just put dirs first and sort them */
1151 eio_dirent *ent = dents + dentoffs;
1152 eio_dirent *dir = dents;
1153
1154 /* now move dirs to the front, and non-dirs to the back */
1155 /* by walking from both sides and swapping if necessary */
1156 while (ent > dir)
1157 {
1158 if (dir->type == DT_DIR)
1159 ++dir;
1160 else
1161 {
1162 --ent;
1163
1164 if (ent->type == DT_DIR)
1165 {
1166 eio_dirent tmp = *dir;
1167 *dir = *ent;
1168 *ent = tmp;
1169
1170 ++dir;
1171 }
1172 }
1173 }
1174
1175 /* now sort the dirs only */
1176 eio_dent_sort (dents, dir - dents);
1177 }
1178
1179 /* only provide the names array unless DENTS is specified */
1180 if (!(flags & EIO_READDIR_DENTS))
1181 {
1182 X_LOCK (wrklock);
1183 assert (!dents);
1184 req->ptr1 = 0;
1185 req->ptr2 = names;
1186 X_UNLOCK (wrklock);
1187 }
1188
991 break; 1189 break;
1190 }
992 1191
1192 /* now add the entry to our list(s) */
993 name = entp->d_name; 1193 name = entp->d_name;
994 1194
1195 /* skip . and .. entries */
995 if (name [0] != '.' || (name [1] && (name [1] != '.' || name [2]))) 1196 if (name [0] != '.' || (name [1] && (name [1] != '.' || name [2])))
996 { 1197 {
997 int len = strlen (name) + 1; 1198 int len = D_NAMLEN (entp) + 1;
998 1199
999 res++; 1200 while (expect_false (namesoffs + len > namesalloc))
1000
1001 while (memofs + len > memlen)
1002 { 1201 {
1003 memlen *= 2; 1202 namesalloc *= 2;
1004 X_LOCK (wrklock); 1203 X_LOCK (wrklock);
1005 req->ptr2 = names = realloc (names, memlen); 1204 req->ptr1 = names = realloc (names, namesalloc);
1006 X_UNLOCK (wrklock); 1205 X_UNLOCK (wrklock);
1007 1206
1008 if (!names) 1207 if (!names)
1009 break; 1208 break;
1010 } 1209 }
1011 1210
1012 memcpy (names + memofs, name, len); 1211 memcpy (names + namesoffs, name, len);
1212
1213 if (dents)
1214 {
1215 struct eio_dirent *ent;
1216
1217 if (expect_false (dentoffs == dentalloc))
1218 {
1219 dentalloc *= 2;
1220 X_LOCK (wrklock);
1221 req->ptr2 = dents = realloc (dents, dentalloc * sizeof (eio_dirent));
1222 X_UNLOCK (wrklock);
1223
1224 if (!dents)
1225 break;
1226 }
1227
1228 ent = dents + dentoffs;
1229
1230 ent->name = (char *)(size_t)namesoffs; /* rather dirtily we store the offset in the pointer */
1231 ent->namelen = len - 1;
1232 ent->inode = D_INO (entp);
1233
1234 switch (D_TYPE (entp))
1235 {
1236 default:
1237 ent->type = EIO_DT_UNKNOWN;
1238 flags |= EIO_READDIR_FOUND_UNKNOWN;
1239 break;
1240
1241 #ifdef DT_FIFO
1242 case DT_FIFO: ent->type = EIO_DT_FIFO; break;
1243 #endif
1244 #ifdef DT_CHR
1245 case DT_CHR: ent->type = EIO_DT_CHR; break;
1246 #endif
1247 #ifdef DT_MPC
1248 case DT_MPC: ent->type = EIO_DT_MPC; break;
1249 #endif
1250 #ifdef DT_DIR
1251 case DT_DIR: ent->type = EIO_DT_DIR; break;
1252 #endif
1253 #ifdef DT_NAM
1254 case DT_NAM: ent->type = EIO_DT_NAM; break;
1255 #endif
1256 #ifdef DT_BLK
1257 case DT_BLK: ent->type = EIO_DT_BLK; break;
1258 #endif
1259 #ifdef DT_MPB
1260 case DT_MPB: ent->type = EIO_DT_MPB; break;
1261 #endif
1262 #ifdef DT_REG
1263 case DT_REG: ent->type = EIO_DT_REG; break;
1264 #endif
1265 #ifdef DT_NWK
1266 case DT_NWK: ent->type = EIO_DT_NWK; break;
1267 #endif
1268 #ifdef DT_CMP
1269 case DT_CMP: ent->type = EIO_DT_CMP; break;
1270 #endif
1271 #ifdef DT_LNK
1272 case DT_LNK: ent->type = EIO_DT_LNK; break;
1273 #endif
1274 #ifdef DT_SOCK
1275 case DT_SOCK: ent->type = EIO_DT_SOCK; break;
1276 #endif
1277 #ifdef DT_DOOR
1278 case DT_DOOR: ent->type = EIO_DT_DOOR; break;
1279 #endif
1280 #ifdef DT_WHT
1281 case DT_WHT: ent->type = EIO_DT_WHT; break;
1282 #endif
1283 }
1284
1285 ent->score = 0;
1286
1287 if (flags & EIO_READDIR_DIRS_FIRST)
1288 {
1289 if (ent->type == EIO_DT_UNKNOWN)
1290 {
1291 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
1292 ent->score = 98;
1293 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
1294 ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */
1295 }
1296 else if (ent->type == EIO_DT_DIR)
1297 ent->score = 100;
1298 }
1299 }
1300
1013 memofs += len; 1301 namesoffs += len;
1302 ++dentoffs;
1303 }
1304
1305 if (EIO_CANCELLED (req))
1306 {
1307 errno = ECANCELED;
1308 break;
1014 } 1309 }
1015 } 1310 }
1016
1017 if (errno)
1018 res = -1;
1019
1020 req->result = res;
1021} 1311}
1022 1312
1023#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO) 1313#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO)
1024# undef msync 1314# undef msync
1025# define msync(a,b,c) ((errno = ENOSYS), -1) 1315# define msync(a,b,c) ((errno = ENOSYS), -1)
1445eio_req *eio_rmdir (const char *path, int pri, eio_cb cb, void *data) 1735eio_req *eio_rmdir (const char *path, int pri, eio_cb cb, void *data)
1446{ 1736{
1447 return eio__1path (EIO_RMDIR, path, pri, cb, data); 1737 return eio__1path (EIO_RMDIR, path, pri, cb, data);
1448} 1738}
1449 1739
1450eio_req *eio_readdir (const char *path, int pri, eio_cb cb, void *data) 1740eio_req *eio_readdir (const char *path, int flags, int pri, eio_cb cb, void *data)
1451{ 1741{
1452 return eio__1path (EIO_READDIR, path, pri, cb, data); 1742 REQ (EIO_READDIR); PATH; req->int1 = flags; SEND;
1453} 1743}
1454 1744
1455eio_req *eio_mknod (const char *path, mode_t mode, dev_t dev, int pri, eio_cb cb, void *data) 1745eio_req *eio_mknod (const char *path, mode_t mode, dev_t dev, int pri, eio_cb cb, void *data)
1456{ 1746{
1457 REQ (EIO_MKNOD); PATH; req->int2 = (long)mode; req->int3 = (long)dev; SEND; 1747 REQ (EIO_MKNOD); PATH; req->int2 = (long)mode; req->int3 = (long)dev; SEND;
1546/* misc garbage */ 1836/* misc garbage */
1547 1837
1548ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1838ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1549{ 1839{
1550 etp_worker wrk; 1840 etp_worker wrk;
1841 ssize_t ret;
1551 1842
1552 wrk.dbuf = 0; 1843 wrk.dbuf = 0;
1553 1844
1554 eio__sendfile (ofd, ifd, offset, count, &wrk); 1845 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1555 1846
1556 if (wrk.dbuf) 1847 if (wrk.dbuf)
1557 free (wrk.dbuf); 1848 free (wrk.dbuf);
1558}
1559 1849
1850 return ret;
1851}
1852

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines