--- libeio/eio.c 2009/06/12 20:01:42 1.38 +++ libeio/eio.c 2010/01/02 12:50:22 1.45 @@ -82,11 +82,11 @@ # include /* POSIX_SOURCE is useless on bsd's, and XOPEN_SOURCE is unreliable there, too */ -# if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) +# if __freebsd || defined __NetBSD__ || defined __OpenBSD__ # define _DIRENT_HAVE_D_TYPE /* sigh */ # define D_INO(de) (de)->d_fileno # define D_NAMLEN(de) (de)->d_namlen -# elif defined(__linux) || defined(d_ino) || _XOPEN_SOURCE >= 600 +# elif __linux || defined d_ino || _XOPEN_SOURCE >= 600 # define D_INO(de) (de)->d_ino # endif @@ -108,13 +108,14 @@ #if HAVE_SENDFILE # if __linux # include -# elif __freebsd +# elif __freebsd || defined __APPLE__ # include # include # elif __hpux # include -# elif __solaris /* not yet */ +# elif __solaris # include +# elif defined _WIN32 # else # error sendfile support requested but not available # endif @@ -198,7 +199,7 @@ #define ETP_NUM_PRI (ETP_PRI_MAX - ETP_PRI_MIN + 1) -/* calculcate time difference in ~1/EIO_TICKS of a second */ +/* calculate time difference in ~1/EIO_TICKS of a second */ static int tvdiff (struct timeval *tv1, struct timeval *tv2) { return (tv2->tv_sec - tv1->tv_sec ) * EIO_TICKS @@ -600,7 +601,7 @@ static void etp_set_max_poll_time (double nseconds) { if (WORDACCESS_UNSAFE) X_LOCK (reslock); - max_poll_time = nseconds; + max_poll_time = nseconds * EIO_TICKS; if (WORDACCESS_UNSAFE) X_UNLOCK (reslock); } @@ -869,7 +870,7 @@ #endif /* even though we could play tricks with the flags, it's better to always - * call fdatasync, as thta matches the expectation of it's users best */ + * call fdatasync, as that matches the expectation of its users best */ return fdatasync (fd); } @@ -925,6 +926,16 @@ res = sbytes; } +# elif defined __APPLE__ + + { + off_t bytes = count; + res = sendfile (ifd, ofd, offset, &bytes, 0, 0); + + if (res < 0 && errno == EAGAIN && bytes) + res = sbytes; + } + # elif __hpux res = sendfile (ofd, ifd, offset, count, 0, 0); @@ -945,6 +956,15 @@ } # endif +#elif defined _WIN32 + + /* does not work, just for documentation of what would need to be done */ + { + HANDLE h = TO_SOCKET (ifd); + SetFilePointer (h, offset, 0, FILE_BEGIN); + res = TransmitFile (TO_SOCKET (ofd), h, count, 0, 0, 0, 0); + } + #else res = -1; errno = ENOSYS; @@ -995,80 +1015,164 @@ static signed char eio_dent_cmp (const eio_dirent *a, const eio_dirent *b) { - return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */ - : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0; + return a->score - b->score ? a->score - b->score /* works because our signed char is always 0..100 */ + : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0; } -#define EIO_QSORT_CUTOFF 20 /* quite high, but performs well on many filesystems */ +#define EIO_DENT_CMP(i,op,j) eio_dent_cmp (&i, &j) op 0 + +#define EIO_SORT_CUTOFF 30 /* quite high, but performs well on many filesystems */ +#define EIO_SORT_FAST 60 /* when to only use insertion sort */ static void -eio_dent_sort (eio_dirent *dents, int size) +eio_dent_radix_sort (eio_dirent *dents, int size, signed char score_bits, ino_t inode_bits) { - int i, j; + unsigned char bits [9 + sizeof (ino_t) * 8]; + unsigned char *bit = bits; - if (size > EIO_QSORT_CUTOFF * 3) /* skip quicksort for small directories */ - { - /* first, use quicksort */ - /* should be good for 2**31 entries */ - struct rng { int l, r; } rng [32]; - - i = 0; - rng[0].l = 0; - rng[0].r = size; + assert (CHAR_BIT == 8); + assert (sizeof (eio_dirent) * 8 < 256); + assert (offsetof (eio_dirent, inode)); /* we use 0 as sentinel */ + assert (offsetof (eio_dirent, score)); /* we use 0 as sentinel */ - while (expect_true (i >= 0)) - { - int L = rng [i].l; - int R = rng [i].r - 1; + if (size <= EIO_SORT_FAST) + return; - if (expect_false (L + EIO_QSORT_CUTOFF < R)) - { - eio_dirent piv = dents [L]; + /* first prepare an array of bits to test in our radix sort */ + /* try to take endianness into account, as well as differences in ino_t sizes */ + /* inode_bits must contain all inodes ORed together */ + /* which is used to skip bits that are 0 everywhere, which is very common */ + { + ino_t endianness; + int i, j; - while (L < R) - { - while (eio_dent_cmp (&dents [R], &piv) >= 0 && L < R) - --R; + /* we store the byte offset of byte n into byte n of "endianness" */ + for (i = 0; i < sizeof (ino_t); ++i) + ((unsigned char *)&endianness)[i] = i; - if (L < R) - dents [L++] = dents [R]; + *bit++ = 0; - while (eio_dent_cmp (&dents [L], &piv) <= 0 && L < R) - ++L; + for (i = 0; i < sizeof (ino_t); ++i) + { + /* shifting off the byte offsets out of "endianness" */ + int offs = (offsetof (eio_dirent, inode) + (endianness & 0xff)) * 8; + endianness >>= 8; + + for (j = 0; j < 8; ++j) + if (inode_bits & (((ino_t)1) << (i * 8 + j))) + *bit++ = offs + j; + } - if (L < R) - dents [R--] = dents [L]; - } + for (j = 0; j < 8; ++j) + if (score_bits & (1 << j)) + *bit++ = offsetof (eio_dirent, score) * 8 + j; + } - dents [L] = piv; + /* now actually do the sorting (a variant of MSD radix sort) */ + { + eio_dirent *base_stk [9 + sizeof (ino_t) * 8], *base; + eio_dirent *end_stk [9 + sizeof (ino_t) * 8], *end; + unsigned char *bit_stk [9 + sizeof (ino_t) * 8]; + int stk_idx = 0; + + base_stk [stk_idx] = dents; + end_stk [stk_idx] = dents + size; + bit_stk [stk_idx] = bit - 1; - ++i; - rng [i].l = L + 1; - rng [i].r = rng [i - 1].r; - rng [i - 1].r = L; + do + { + base = base_stk [stk_idx]; + end = end_stk [stk_idx]; + bit = bit_stk [stk_idx]; - if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l) - { - struct rng t; + for (;;) + { + unsigned char O = *bit >> 3; + unsigned char M = 1 << (*bit & 7); + + eio_dirent *a = base; + eio_dirent *b = end; - t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t; + if (b - a < EIO_SORT_CUTOFF) + break; + + /* now bit-partition the array on the bit */ + /* this ugly asymmetric loop seems to perform much better than typical */ + /* partition algos found in the literature */ + do + if (!(((unsigned char *)a)[O] & M)) + ++a; + else if (!(((unsigned char *)--b)[O] & M)) + { + eio_dirent tmp = *a; *a = *b; *b = tmp; + ++a; } - } - else - --i; - } - } + while (b > a); - /* use a simple insertion sort at the end */ - for (i = 1; i < size; ++i) - { - eio_dirent value = dents [i]; + /* next bit, or stop, if no bits left in this path */ + if (!*--bit) + break; - for (j = i - 1; j >= 0 && eio_dent_cmp (&dents [j], &value) > 0; --j) - dents [j + 1] = dents [j]; + base_stk [stk_idx] = a; + end_stk [stk_idx] = end; + bit_stk [stk_idx] = bit; + ++stk_idx; + + end = a; + } + } + while (stk_idx--); + } +} - dents [j + 1] = value; +static void +eio_dent_insertion_sort (eio_dirent *dents, int size) +{ + /* first move the smallest element to the front, to act as a sentinel */ + { + int i; + eio_dirent *min = dents; + + /* the radix pre-pass ensures that the minimum element is in the first EIO_SORT_CUTOFF + 1 elements */ + for (i = size > EIO_SORT_FAST ? EIO_SORT_CUTOFF + 1 : size; --i; ) + if (EIO_DENT_CMP (dents [i], <, *min)) + min = &dents [i]; + + /* swap elements 0 and j (minimum) */ + { + eio_dirent tmp = *dents; *dents = *min; *min = tmp; } + } + + /* then do standard insertion sort, assuming that all elements are >= dents [0] */ + { + eio_dirent *i, *j; + + for (i = dents + 1; i < dents + size; ++i) + { + eio_dirent value = *i; + + for (j = i - 1; EIO_DENT_CMP (*j, >, value); --j) + j [1] = j [0]; + + j [1] = value; + } + } +} + +static void +eio_dent_sort (eio_dirent *dents, int size, signed char score_bits, ino_t inode_bits) +{ + if (size <= 1) + return; /* our insertion sort relies on size > 0 */ + + /* first we use a radix sort, but only for dirs >= EIO_SORT_FAST */ + /* and stop sorting when the partitions are <= EIO_SORT_CUTOFF */ + eio_dent_radix_sort (dents, size, score_bits, inode_bits); + + /* use an insertion sort at the end, or for small arrays, */ + /* as insertion sort is more efficient for small partitions */ + eio_dent_insertion_sort (dents, size); } /* read a full directory */ @@ -1084,6 +1188,7 @@ eio_dirent *dents = 0; int dentalloc = 128; int dentoffs = 0; + ino_t inode_bits = 0; req->result = -1; @@ -1094,8 +1199,8 @@ /* the corresponding closedir is in ETP_WORKER_CLEAR */ self->dirp = dirp = opendir (req->ptr1); req->flags |= EIO_FLAG_PTR1_FREE | EIO_FLAG_PTR2_FREE; - req->ptr1 = names = malloc (namesalloc); - req->ptr2 = dents = flags ? malloc (dentalloc * sizeof (eio_dirent)) : 0; + req->ptr1 = dents = flags ? malloc (dentalloc * sizeof (eio_dirent)) : 0; + req->ptr2 = names = malloc (namesalloc); X_UNLOCK (wrklock); if (dirp && names && (!flags || dents)) @@ -1113,57 +1218,35 @@ req->int1 = flags; req->result = dentoffs; - if (dents) - { - eio_dirent *ent = dents + dentoffs; - - while (ent > dents) - (--ent)->name = names + (size_t)ent->name; - } - - if (flags & EIO_READDIR_STAT_ORDER - || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN))) - eio_dent_sort (dents, dentoffs); /* score depends of DIRS_FIRST */ + if (flags & EIO_READDIR_STAT_ORDER) + eio_dent_sort (dents, dentoffs, 0, inode_bits); /* sort by inode exclusively */ else if (flags & EIO_READDIR_DIRS_FIRST) - { - /* in this case, all is known, and we just put dirs first and sort them */ - eio_dirent *ent = dents + dentoffs; - eio_dirent *dir = dents; - - /* now move dirs to the front, and non-dirs to the back */ - /* by walking from both sides and swapping if necessary */ - while (ent > dir) - { - if (dir->type == DT_DIR) - ++dir; - else - { - --ent; - - if (ent->type == DT_DIR) - { - eio_dirent tmp = *dir; - *dir = *ent; - *ent = tmp; - - ++dir; - } - } - } - - /* now sort the dirs only */ - eio_dent_sort (dents, dir - dents); - } + if (flags & EIO_READDIR_FOUND_UNKNOWN) + eio_dent_sort (dents, dentoffs, 7, inode_bits); /* sort by score and inode */ + else + { + /* in this case, all is known, and we just put dirs first and sort them */ + eio_dirent *oth = dents + dentoffs; + eio_dirent *dir = dents; + + /* now partition dirs to the front, and non-dirs to the back */ + /* by walking from both sides and swapping if necessary */ + /* also clear score, so it doesn't influence sorting */ + while (oth > dir) + { + if (dir->type == EIO_DT_DIR) + ++dir; + else if ((--oth)->type == EIO_DT_DIR) + { + eio_dirent tmp = *dir; *dir = *oth; *oth = tmp; + + ++dir; + } + } - /* only provide the names array unless DENTS is specified */ - if (!(flags & EIO_READDIR_DENTS)) - { - X_LOCK (wrklock); - assert (!dents); - req->ptr1 = 0; - req->ptr2 = names; - X_UNLOCK (wrklock); - } + /* now sort the dirs only */ + eio_dent_sort (dents, dir - dents, 0, inode_bits); + } break; } @@ -1180,7 +1263,7 @@ { namesalloc *= 2; X_LOCK (wrklock); - req->ptr1 = names = realloc (names, namesalloc); + req->ptr2 = names = realloc (names, namesalloc); X_UNLOCK (wrklock); if (!names) @@ -1197,7 +1280,7 @@ { dentalloc *= 2; X_LOCK (wrklock); - req->ptr2 = dents = realloc (dents, dentalloc * sizeof (eio_dirent)); + req->ptr1 = dents = realloc (dents, dentalloc * sizeof (eio_dirent)); X_UNLOCK (wrklock); if (!dents) @@ -1206,10 +1289,12 @@ ent = dents + dentoffs; - ent->name = (char *)(size_t)namesoffs; /* rather dirtily we store the offset in the pointer */ + ent->nameofs = namesoffs; /* rather dirtily we store the offset in the pointer */ ent->namelen = len - 1; ent->inode = D_INO (entp); + inode_bits |= ent->inode; + switch (D_TYPE (entp)) { default: @@ -1261,19 +1346,19 @@ #endif } - ent->score = 0; + ent->score = 7; if (flags & EIO_READDIR_DIRS_FIRST) { if (ent->type == EIO_DT_UNKNOWN) { if (*name == '.') /* leading dots are likely directories, and, in any case, rare */ - ent->score = 98; + ent->score = 1; else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */ - ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */ + ent->score = len <= 2 ? 4 - len : len <= 4 ? 4 : len <= 7 ? 5 : 6; /* shorter == more likely dir, but avoid too many classes */ } else if (ent->type == EIO_DT_DIR) - ent->score = 100; + ent->score = 0; } } @@ -1308,6 +1393,7 @@ page = sysconf (_SC_PAGESIZE); #endif + /* round down to start of page, although this is probably useless */ addr &= ~(page - 1); /* assume page size is always a power of two */ if (addr < end)