Updated to fedora-glibc-20041210T0634

11 files changed, 259 insertions, 154 deletions

diff --git a/ChangeLog b/ChangeLog
index 75a4f15a4d..4b5c3dca03 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,9 +1,58 @@
+2004-11-29  Jakub Jelinek  <jakub@redhat.com>
+
+	* stdlib/strtod_l.c (INTERNAL (__STRTOF)): If densize > 2
+	and numsize < densize, always shift num up by empty + 1 limbs.
+
+2004-12-07  Paolo Bonzini  <bonzini@gnu.org>
+
+	* posix/regexec.c (proceed_next_node): Simplify treatment of epsilon
+	nodes.  Pass the pushed node to push_fail_stack.
+	(push_fail_stack): Accept a single node rather than an array
+	of two epsilon destinations.
+	(build_sifted_states): Only walk non-epsilon nodes.
+	(check_arrival): Don't pass epsilon nodes to
+	check_arrival_add_next_nodes.
+	(check_arrival_add_next_nodes) [DEBUG]: Abort if an epsilon node is
+	found.
+	(check_node_accept): Do expensive checks later.
+	(add_epsilon_src_nodes): Cache result of merging the inveclosures.
+	* posix/regex_internal.h (re_dfastate_t): Add non_eps_nodes and
+	inveclosure.
+	(re_string_elem_size_at, re_string_char_size_at, re_string_wchar_at,
+	re_string_context_at, re_string_peek_byte_case,
+	re_string_fetch_byte_case, re_node_set_compare, re_node_set_contains):
+	Declare as pure.
+	* posix/regex_internal.c (create_newstate_common): Remove.
+	(register_state): Move part of it here.  Initialize non_eps_nodes.
+	(free_state): Free inveclosure and non_eps_nodes.
+	(create_cd_newstate, create_ci_newstate): Allocate the new
+	re_dfastate_t here.
+
+2004-12-09  Ulrich Drepper  <drepper@redhat.com>
+
+	* malloc/malloc.c (public_rEALLOc): Add parameter checks.
+	(_int_free): Provide better error message for invalid pointers.
+
+2004-12-01  Jakub Jelinek  <jakub@redhat.com>
+
+	* posix/tst-regex.c: Use defined _POSIX_CPUTIME && _POSIX_CPUTIME >= 0
+	conditionals instead of defined _POSIX_CPUTIME.
+	(main): If _POSIX_CPUTIME == 0, call sysconf to see if CPUTIME
+	option is available.
+	* posix/tst-regex.c2: Use defined _POSIX_CPUTIME && _POSIX_CPUTIME >= 0
+	conditionals instead of defined _POSIX_CPUTIME.
+	(do_test): If _POSIX_CPUTIME == 0, call sysconf to see if CPUTIME
+	option is available.
+	* sysdeps/posix/sysconf.c (__sysconf): If _POSIX_CPUTIME resp.
+	_POSIX_THREAD_CPUTIME is defined to 0, return -1 for the corresponding
+	_SC_ argument.
+
 2004-12-08  Jakub Jelinek  <jakub@redhat.com>
 
-	* elf/ldd.bash.in: For -u, set bind_now=yes.
-	If eval $add_env '"$file"' exits with exitcode 5, retry with
-	eval $add_env \${RTLD} '"$file"'.
-	Remove | cat usage, it breaks exit code propagation.
+	* elf/ldd.bash.in: When set -o pipefail is available, use that for
+	piping to cat; when not, don't use the pipe at all.
+	Pipe to cat in all cases of running the executable.
+	When direct running exits with code 5, retry running via ${RTLD}.
 	* elf/rtld.c (process_envvars): If __libc_enable_secure and
 	mode != normal, exit with exitcode 5.
 
@@ -130,20 +179,6 @@
 	* sysdeps/unix/sysv/linux/arm/sysdep.h: Likewise.
 	* sysdeps/unix/sysv/linux/arm/vfork.S: Likewise.
 
-2004-12-01  Jakub Jelinek  <jakub@redhat.com>
-
-	* posix/tst-regex.c: Use defined _POSIX_CPUTIME && _POSIX_CPUTIME >= 0
-	conditionals instead of defined _POSIX_CPUTIME.
-	(main): If _POSIX_CPUTIME == 0, call sysconf to see if CPUTIME
-	option is available.
-	* posix/tst-regex.c2: Use defined _POSIX_CPUTIME && _POSIX_CPUTIME >= 0
-	conditionals instead of defined _POSIX_CPUTIME.
-	(do_test): If _POSIX_CPUTIME == 0, call sysconf to see if CPUTIME
-	option is available.
-	* sysdeps/posix/sysconf.c (__sysconf): If _POSIX_CPUTIME resp.
-	_POSIX_THREAD_CPUTIME is defined to 0, return -1 for the corresponding
-	_SC_ argument.
-
 2004-12-02  Roland McGrath  <roland@redhat.com>
 
 	* extra-lib.mk (object-suffixes-$(lib)): Add .oS when
@@ -172,12 +207,6 @@
 	* sysdeps/gnu/Makefile ($(objpfx)errlist-compat.c):
 	Do $(make-target-directory).
 
-2004-11-29  Jakub Jelinek  <jakub@redhat.com>
-
-	* stdlib/strtod_l.c (INTERNAL (__STRTOF)): If densize > 2
-	and numsize < densize, always shift num up by empty + 1
-	limbs.
-
 2004-11-29  Roland McGrath  <roland@redhat.com>
 
 	* posix/confstr.c: Avoid punctuation in #error text.
diff --git a/elf/ldd.bash.in b/elf/ldd.bash.in
index c91886a1e6..5dbf88cdc8 100644
--- a/elf/ldd.bash.in
+++ b/elf/ldd.bash.in
@@ -106,6 +106,21 @@ add_env="$add_env LD_VERBOSE=$verbose"
 if test "$unused" = yes; then
   add_env="$add_env LD_DEBUG=\"$LD_DEBUG${LD_DEBUG:+,}unused\""
 fi
+
+# The following use of cat is needed to make ldd work in SELinux
+# environments where the executed program might not have permissions
+# to write to the console/tty.  But only bash 3.x supports the pipefail
+# option, and we don't bother to handle the case for older bash versions.
+if set -o pipefail 2> /dev/null; then
+  try_trace() {
+    eval $add_env '"$@"' | cat
+  }
+else
+  try_trace() {
+    eval $add_env '"$@"'
+  }
+fi
+
 case $# in
 0)
   echo >&2 'ldd:' $"missing file arguments"
@@ -157,8 +172,13 @@ warning: you do not have execution permission for" "\`$file'" >&2
       # If the program exits with exit code 5, it means the process has been
       # invoked with __libc_enable_secure.  Fall back to running it through
       # the dynamic linker.
-      ( eval $add_env '"$file"'; ret=$?; [ $ret != 5 ] && exit $ret;
-        eval $add_env \${RTLD} '"$file"'; ) || result=1
+      try_trace "$file"
+      rc=$?
+      if [ $rc = 5 ]; then
+	try_trace "$RTLD" "$file"
+	rc=$?
+      fi
+      [ $rc = 0 ] || result=1
       ;;
     1)
       # This can be a non-ELF binary or no binary at all.
@@ -168,7 +188,7 @@ warning: you do not have execution permission for" "\`$file'" >&2
       }
       ;;
     2)
-      eval $add_env \${RTLD} '"$file"' || result=1
+      try_trace "$RTLD" "$file" || result=1
       ;;
     *)
       echo 'ldd:' ${RTLD} $"exited with unknown exit code" "($ret)" >&2
diff --git a/fedora/branch.mk b/fedora/branch.mk
index e493d062a6..653f1e4aa7 100644
--- a/fedora/branch.mk
+++ b/fedora/branch.mk
@@ -1,5 +1,5 @@
 # This file is updated automatically by Makefile.
 glibc-branch := fedora
 glibc-base := HEAD
-fedora-sync-date := 2004-12-08 10:24 UTC
-fedora-sync-tag := fedora-glibc-20041208T1024
+fedora-sync-date := 2004-12-10 06:34 UTC
+fedora-sync-tag := fedora-glibc-20041210T0634
diff --git a/fedora/glibc.spec.in b/fedora/glibc.spec.in
index 5c3f31c675..2ea3705bba 100644
--- a/fedora/glibc.spec.in
+++ b/fedora/glibc.spec.in
@@ -1,4 +1,4 @@
-%define glibcrelease 89
+%define glibcrelease 90
 %define auxarches i586 i686 athlon sparcv9 alphaev6
 %define prelinkarches noarch
 %define nptlarches i386 i686 athlon x86_64 ia64 s390 s390x sparcv9 ppc ppc64
@@ -1265,6 +1265,12 @@ rm -f *.filelist*
 %endif
 
 %changelog
+* Fri Dec 10 2004 Jakub Jelinek <jakub@redhat.com> 2.3.3-90
+- update from CVS
+  - regex speedups
+  - use | cat in ldd if running under bash3+ to allow running
+    it on binaries that are not through SELinux allowed to access
+    console or tty
 - add __NR_waitid defines for alpha and ia64
 
 * Wed Dec  8 2004 Jakub Jelinek <jakub@redhat.com> 2.3.3-89
diff --git a/linuxthreads/ChangeLog b/linuxthreads/ChangeLog
index 9e34a9768e..1849b8a630 100644
--- a/linuxthreads/ChangeLog
+++ b/linuxthreads/ChangeLog
@@ -1,9 +1,4 @@
-2004-11-18  Daniel Jacobowitz  <dan@codesourcery.com>
-
-	* sysdeps/unix/sysv/linux/arm/sysdep-cancel.h: Update RETINSTR use.
-	* sysdeps/unix/sysv/linux/arm/vfork.S: Likewise.
-
-2004-12-01  Jakub Jelinek  <jakub@redhat.com>
+2004-12-01  Jakub Jelinek  <jakub@redhat.coM.
 
 	* sysdeps/unix/sysv/linux/bits/posix_opt.h (_POSIX_CPUTIME,
 	_POSIX_THREAD_CPUTIME): Define to 0.
@@ -18,6 +13,12 @@
 	* sysdeps/unix/sysv/linux/i386/bits/posix_opt.h: Removed.
 	* sysdeps/unix/sysv/linux/ia64/bits/posix_opt.h: Removed.
 	* sysdeps/unix/sysv/linux/x86_64/bits/posix_opt.h: Removed.
+	* tst-clock1.c (do_test): Check for availability of CPU clock.
+
+2004-11-18  Daniel Jacobowitz  <dan@codesourcery.com>
+
+	* sysdeps/unix/sysv/linux/arm/sysdep-cancel.h: Update RETINSTR use.
+	* sysdeps/unix/sysv/linux/arm/vfork.S: Likewise.
 
 2004-12-02  Roland McGrath  <roland@redhat.com>
 
diff --git a/malloc/malloc.c b/malloc/malloc.c
index b62ffb57c0..cf1b935ffd 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3434,6 +3434,17 @@ public_rEALLOc(Void_t* oldmem, size_t bytes)
   oldp    = mem2chunk(oldmem);
   oldsize = chunksize(oldp);
 
+  /* Little security check which won't hurt performance: the
+     allocator never wrapps around at the end of the address space.
+     Therefore we can exclude some size values which might appear
+     here by accident or by "design" from some intruder.  */
+  if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
+      || __builtin_expect ((uintptr_t) oldp & MALLOC_ALIGN_MASK, 0))
+    {
+      malloc_printerr (check_action, "realloc(): invalid pointer", oldmem);
+      return NULL;
+    }
+
   checked_request2size(bytes, nb);
 
 #if HAVE_MMAP
@@ -4205,7 +4216,6 @@ _int_free(mstate av, Void_t* mem)
   mchunkptr       bck;         /* misc temp for linking */
   mchunkptr       fwd;         /* misc temp for linking */
 
-
   const char *errstr = NULL;
 
   p = mem2chunk(mem);
@@ -4215,7 +4225,8 @@ _int_free(mstate av, Void_t* mem)
      allocator never wrapps around at the end of the address space.
      Therefore we can exclude some size values which might appear
      here by accident or by "design" from some intruder.  */
-  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0))
+  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
+      || __builtin_expect ((uintptr_t) p & MALLOC_ALIGN_MASK, 0))
     {
       errstr = "free(): invalid pointer";
     errout:
diff --git a/nptl/ChangeLog b/nptl/ChangeLog
index 8352c6b904..981781807b 100644
--- a/nptl/ChangeLog
+++ b/nptl/ChangeLog
@@ -1,3 +1,24 @@
+2004-12-09  Ulrich Drepper  <drepper@redhat.com>
+
+	* init.c (__pthread_initialize_minimal_internal): Also unblock
+	SIGSETXID.
+
+2004-12-01  Jakub Jelinek  <jakub@redhat.com>
+
+	* sysdeps/unix/sysv/linux/bits/posix_opt.h (_POSIX_CPUTIME,
+	_POSIX_THREAD_CPUTIME): Define to 0.
+	* sysdeps/pthread/timer_create.c (timer_create): Remove unused code
+	handling CLOCK_PROCESS_CPUTIME_ID and CLOCK_THREAD_CPUTIME_ID.
+	* sysdeps/pthread/timer_routines.c (__timer_signal_thread_pclk,
+	__timer_signal_thread_tclk): Remove.
+	(init_module): Remove their initialization.
+	(thread_cleanup): Remove their cleanup assertions.
+	* sysdeps/pthread/posix-timer.h (__timer_signal_thread_pclk,
+	__timer_signal_thread_tclk): Remove.
+	* sysdeps/unix/sysv/linux/i386/bits/posix_opt.h: Removed.
+	* sysdeps/unix/sysv/linux/ia64/bits/posix_opt.h: Removed.
+	* sysdeps/unix/sysv/linux/x86_64/bits/posix_opt.h: Removed.
+
 2004-12-07  Jakub Jelinek  <jakub@redhat.com>
 
 	* sysdeps/ia64/tcb-offsets.sym (TID): Add.
@@ -19,22 +40,6 @@
 	* sysdeps/unix/sysv/linux/i386/clone.S: New file.
 	* sysdeps/unix/sysv/linux/x86_64/clone.S: New file.
 
-2004-12-01  Jakub Jelinek  <jakub@redhat.com>
-
-	* sysdeps/unix/sysv/linux/bits/posix_opt.h (_POSIX_CPUTIME,
-	_POSIX_THREAD_CPUTIME): Define to 0.
-	* sysdeps/pthread/timer_create.c (timer_create): Remove unused code
-	handling CLOCK_PROCESS_CPUTIME_ID and CLOCK_THREAD_CPUTIME_ID.
-	* sysdeps/pthread/timer_routines.c (__timer_signal_thread_pclk,
-	__timer_signal_thread_tclk): Remove.
-	(init_module): Remove their initialization.
-	(thread_cleanup): Remove their cleanup assertions.
-	* sysdeps/pthread/posix-timer.h (__timer_signal_thread_pclk,
-	__timer_signal_thread_tclk): Remove.
-	* sysdeps/unix/sysv/linux/i386/bits/posix_opt.h: Removed.
-	* sysdeps/unix/sysv/linux/ia64/bits/posix_opt.h: Removed.
-	* sysdeps/unix/sysv/linux/x86_64/bits/posix_opt.h: Removed.
-
 2004-12-02  Roland McGrath  <roland@redhat.com>
 
 	* Makefile (libpthread-nonshared): Variable removed.
diff --git a/nptl/init.c b/nptl/init.c
index a18078edb8..3751e6be77 100644
--- a/nptl/init.c
+++ b/nptl/init.c
@@ -272,10 +272,11 @@ __pthread_initialize_minimal_internal (void)
 
   (void) __libc_sigaction (SIGSETXID, &sa, NULL);
 
-  /* The parent process might have left the signal blocked.  Just in
+  /* The parent process might have left the signals blocked.  Just in
      case, unblock it.  We reuse the signal mask in the sigaction
      structure.  It is already cleared.  */
   __sigaddset (&sa.sa_mask, SIGCANCEL);
+  __sigaddset (&sa.sa_mask, SIGSETXID);
   (void) INTERNAL_SYSCALL (rt_sigprocmask, err, 4, SIG_UNBLOCK, &sa.sa_mask,
 			   NULL, _NSIG / 8);
 
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index cb439e5d7c..001b50b134 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -26,9 +26,6 @@ static void re_string_construct_common (const char *str, int len,
 static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx,
 				 wint_t *last_wc) internal_function;
 #endif /* RE_ENABLE_I18N */
-static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
-					      const re_node_set *nodes,
-					      unsigned int hash) internal_function;
 static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
 				     unsigned int hash) internal_function;
 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
@@ -1298,7 +1295,7 @@ re_node_set_contains (set, elem)
      const re_node_set *set;
      int elem;
 {
-  int idx, right, mid;
+  unsigned int idx, right, mid;
   if (set->nelem <= 0)
     return 0;
 
@@ -1484,43 +1481,32 @@ re_acquire_state_context (err, dfa, nodes, context)
     }
 }
 
-/* Allocate memory for DFA state and initialize common properties.
-   Return the new state if succeeded, otherwise return NULL.  */
+/* Finish initialization of the new state NEWSTATE, and using its hash value
+   HASH put in the appropriate bucket of DFA's state table.  Return value
+   indicates the error code if failed.  */
 
-static re_dfastate_t *
-create_newstate_common (dfa, nodes, hash)
+static reg_errcode_t
+register_state (dfa, newstate, hash)
      re_dfa_t *dfa;
-     const re_node_set *nodes;
+     re_dfastate_t *newstate;
      unsigned int hash;
 {
-  re_dfastate_t *newstate;
+  struct re_state_table_entry *spot;
   reg_errcode_t err;
-  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
-  if (BE (newstate == NULL, 0))
-    return NULL;
-  err = re_node_set_init_copy (&newstate->nodes, nodes);
+  int i;
+
+  newstate->hash = hash;
+  err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem);
   if (BE (err != REG_NOERROR, 0))
+    return REG_ESPACE;
+  for (i = 0; i < newstate->nodes.nelem; i++)
     {
-      re_free (newstate);
-      return NULL;
+      int elem = newstate->nodes.elems[i];
+      if (!IS_EPSILON_NODE (dfa->nodes[elem].type))
+        re_node_set_insert_last (&newstate->non_eps_nodes, elem);
     }
-  newstate->trtable = NULL;
-  newstate->hash = hash;
-  return newstate;
-}
 
-/* Store the new state NEWSTATE whose hash value is HASH in appropriate
-   position.  Return value indicate the error code if failed.  */
-
-static reg_errcode_t
-register_state (dfa, newstate, hash)
-     re_dfa_t *dfa;
-     re_dfastate_t *newstate;
-     unsigned int hash;
-{
-  struct re_state_table_entry *spot;
   spot = dfa->state_table + (hash & dfa->state_hash_mask);
-
   if (BE (spot->alloc <= spot->num, 0))
     {
       int new_alloc = 2 * spot->num + 2;
@@ -1547,11 +1533,18 @@ create_ci_newstate (dfa, nodes, hash)
   int i;
   reg_errcode_t err;
   re_dfastate_t *newstate;
-  newstate = create_newstate_common (dfa, nodes, hash);
+
+  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
   if (BE (newstate == NULL, 0))
     return NULL;
-  newstate->entrance_nodes = &newstate->nodes;
+  err = re_node_set_init_copy (&newstate->nodes, nodes);
+  if (BE (err != REG_NOERROR, 0))
+    {
+      re_free (newstate);
+      return NULL;
+    }
 
+  newstate->entrance_nodes = &newstate->nodes;
   for (i = 0 ; i < nodes->nelem ; i++)
     {
       re_token_t *node = dfa->nodes + nodes->elems[i];
@@ -1595,9 +1588,16 @@ create_cd_newstate (dfa, nodes, context, hash)
   reg_errcode_t err;
   re_dfastate_t *newstate;
 
-  newstate = create_newstate_common (dfa, nodes, hash);
+  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
   if (BE (newstate == NULL, 0))
     return NULL;
+  err = re_node_set_init_copy (&newstate->nodes, nodes);
+  if (BE (err != REG_NOERROR, 0))
+    {
+      re_free (newstate);
+      return NULL;
+    }
+
   newstate->context = context;
   newstate->entrance_nodes = &newstate->nodes;
 
@@ -1660,6 +1660,8 @@ static void
 free_state (state)
      re_dfastate_t *state;
 {
+  re_node_set_free (&state->non_eps_nodes);
+  re_node_set_free (&state->inveclosure);
   if (state->entrance_nodes != &state->nodes)
     {
       re_node_set_free (state->entrance_nodes);
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index 1345067a89..0ccd8d3665 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -388,18 +388,20 @@ static void re_string_translate_buffer (re_string_t *pstr) internal_function;
 static void re_string_destruct (re_string_t *pstr) internal_function;
 # ifdef RE_ENABLE_I18N
 static int re_string_elem_size_at (const re_string_t *pstr, int idx)
-     internal_function;
+     internal_function __attribute ((pure));
 static inline int re_string_char_size_at (const re_string_t *pstr, int idx)
-     internal_function;
+     internal_function __attribute ((pure));
 static inline wint_t re_string_wchar_at (const re_string_t *pstr, int idx)
-     internal_function;
+     internal_function __attribute ((pure));
 # endif /* RE_ENABLE_I18N */
 static unsigned int re_string_context_at (const re_string_t *input, int idx,
-					  int eflags) internal_function;
+					  int eflags)
+     internal_function __attribute ((pure));
 static unsigned char re_string_peek_byte_case (const re_string_t *pstr,
-					       int idx) internal_function;
+					       int idx)
+     internal_function __attribute ((pure));
 static unsigned char re_string_fetch_byte_case (re_string_t *pstr)
-     internal_function;
+     internal_function __attribute ((pure));
 #endif
 #define re_string_peek_byte(pstr, offset) \
   ((pstr)->mbs[(pstr)->cur_idx + offset])
@@ -481,6 +483,8 @@ struct re_dfastate_t
 {
   unsigned int hash;
   re_node_set nodes;
+  re_node_set non_eps_nodes;
+  re_node_set inveclosure;
   re_node_set *entrance_nodes;
   struct re_dfastate_t **trtable;
   unsigned int context : 4;
@@ -665,8 +669,10 @@ static int re_node_set_insert (re_node_set *set, int elem) internal_function;
 static int re_node_set_insert_last (re_node_set *set,
 				    int elem) internal_function;
 static int re_node_set_compare (const re_node_set *set1,
-				const re_node_set *set2) internal_function;
-static int re_node_set_contains (const re_node_set *set, int elem) internal_function;
+				const re_node_set *set2)
+     internal_function __attribute ((pure));
+static int re_node_set_contains (const re_node_set *set, int elem)
+     internal_function __attribute ((pure));
 static void re_node_set_remove_at (re_node_set *set, int idx) internal_function;
 #define re_node_set_remove(set,id) \
   (re_node_set_remove_at (set, re_node_set_contains (set, id) - 1))
diff --git a/posix/regexec.c b/posix/regexec.c
index 22b806439b..91b48dd4a2 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -73,7 +73,7 @@ static int proceed_next_node (const re_match_context_t *mctx,
 			      int *pidx, int node, re_node_set *eps_via_nodes,
 			      struct re_fail_stack_t *fs) internal_function;
 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
-				      int str_idx, int *dests, int nregs,
+				      int str_idx, int dest_node, int nregs,
 				      regmatch_t *regs,
 				      re_node_set *eps_via_nodes) internal_function;
 static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
@@ -1223,30 +1223,38 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
   if (IS_EPSILON_NODE (dfa->nodes[node].type))
     {
       re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
-      int ndest, dest_nodes[2];
+      re_node_set *edests = &dfa->edests[node];
+      int dest_node;
       err = re_node_set_insert (eps_via_nodes, node);
       if (BE (err < 0, 0))
 	return -2;
-      /* Pick up valid destinations.  */
-      for (ndest = 0, i = 0; i < dfa->edests[node].nelem; ++i)
+      /* Pick up a valid destination, or return -1 if none is found.  */
+      for (dest_node = -1, i = 0; i < edests->nelem; ++i)
 	{
-	  int candidate = dfa->edests[node].elems[i];
+	  int candidate = edests->elems[i];
 	  if (!re_node_set_contains (cur_nodes, candidate))
 	    continue;
-	  dest_nodes[0] = (ndest == 0) ? candidate : dest_nodes[0];
-	  dest_nodes[1] = (ndest == 1) ? candidate : dest_nodes[1];
-	  ++ndest;
+          if (dest_node == -1)
+	    dest_node = candidate;
+
+          else
+	    {
+	      /* In order to avoid infinite loop like "(a*)*", return the second
+	         epsilon-transition if the first was already considered.  */
+	      if (re_node_set_contains (eps_via_nodes, dest_node))
+	        return candidate;
+
+	      /* Otherwise, push the second epsilon-transition on the fail stack.  */
+	      else if (fs != NULL
+		       && push_fail_stack (fs, *pidx, candidate, nregs, regs,
+				           eps_via_nodes))
+		return -2;
+
+	      /* We know we are going to exit.  */
+	      break;
+	    }
 	}
-      if (ndest <= 1)
-	return ndest == 0 ? -1 : (ndest == 1 ? dest_nodes[0] : 0);
-      /* In order to avoid infinite loop like "(a*)*".  */
-      if (re_node_set_contains (eps_via_nodes, dest_nodes[0]))
-	return dest_nodes[1];
-      if (fs != NULL
-	  && push_fail_stack (fs, *pidx, dest_nodes, nregs, regs,
-			      eps_via_nodes))
-	return -2;
-      return dest_nodes[0];
+      return dest_node;
     }
   else
     {
@@ -1304,9 +1312,9 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
 }
 
 static reg_errcode_t
-push_fail_stack (fs, str_idx, dests, nregs, regs, eps_via_nodes)
+push_fail_stack (fs, str_idx, dest_node, nregs, regs, eps_via_nodes)
      struct re_fail_stack_t *fs;
-     int str_idx, *dests, nregs;
+     int str_idx, dest_node, nregs;
      regmatch_t *regs;
      re_node_set *eps_via_nodes;
 {
@@ -1323,7 +1331,7 @@ push_fail_stack (fs, str_idx, dests, nregs, regs, eps_via_nodes)
       fs->stack = new_array;
     }
   fs->stack[num].idx = str_idx;
-  fs->stack[num].node = dests[1];
+  fs->stack[num].node = dest_node;
   fs->stack[num].regs = re_malloc (regmatch_t, nregs);
   if (fs->stack[num].regs == NULL)
     return REG_ESPACE;
@@ -1600,7 +1608,7 @@ build_sifted_states (mctx, sctx, str_idx, cur_dest)
      re_node_set *cur_dest;
 {
   re_dfa_t *const dfa = mctx->dfa;
-  re_node_set *cur_src = &mctx->state_log[str_idx]->nodes;
+  re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
   int i;
 
   /* Then build the next sifted state.
@@ -1608,16 +1616,20 @@ build_sifted_states (mctx, sctx, str_idx, cur_dest)
      `sifted_states[str_idx]' with `cur_dest'.
      Note:
      `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
-     `cur_src' points the node_set of the old `state_log[str_idx]'.  */
+     `cur_src' points the node_set of the old `state_log[str_idx]'
+     (with the epsilon nodes pre-filtered out).  */
   for (i = 0; i < cur_src->nelem; i++)
     {
       int prev_node = cur_src->elems[i];
       int naccepted = 0;
-      re_token_type_t type = dfa->nodes[prev_node].type;
       int ret;
 
-      if (IS_EPSILON_NODE (type))
-	continue;
+#if defined DEBUG || defined RE_ENABLE_I18N
+      re_token_type_t type = dfa->nodes[prev_node].type;
+#endif
+#ifdef DEBUG
+      assert (!IS_EPSILON_NODE (type));
+#endif
 #ifdef RE_ENABLE_I18N
       /* If the node may accept `multi byte'.  */
       if (ACCEPT_MB_NODE (type))
@@ -1764,26 +1776,24 @@ add_epsilon_src_nodes (dfa, dest_nodes, candidates)
      re_node_set *dest_nodes;
      const re_node_set *candidates;
 {
-  reg_errcode_t err;
-  int src_idx;
-  re_node_set src_copy;
+  reg_errcode_t err = REG_NOERROR;
+  int i;
 
-  err = re_node_set_init_copy (&src_copy, dest_nodes);
+  re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
   if (BE (err != REG_NOERROR, 0))
     return err;
-  for (src_idx = 0; src_idx < src_copy.nelem; ++src_idx)
+
+  if (!state->inveclosure.alloc)
     {
-      err = re_node_set_add_intersect (dest_nodes, candidates,
-				       dfa->inveclosures
-				       + src_copy.elems[src_idx]);
+      err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
       if (BE (err != REG_NOERROR, 0))
-	{
-	  re_node_set_free (&src_copy);
-	  return err;
-	}
+        return REG_ESPACE;
+      for (i = 0; i < dest_nodes->nelem; i++)
+        re_node_set_merge (&state->inveclosure,
+			   dfa->inveclosures + dest_nodes->elems[i]);
     }
-  re_node_set_free (&src_copy);
-  return REG_NOERROR;
+  return re_node_set_add_intersect (dest_nodes, candidates,
+				    &state->inveclosure);
 }
 
 static reg_errcode_t
@@ -2935,7 +2945,7 @@ check_arrival (mctx, path, top_node, top_str, last_node, last_str,
       if (cur_state)
 	{
 	  err = check_arrival_add_next_nodes (mctx, str_idx,
-					      &cur_state->nodes, &next_nodes);
+					      &cur_state->non_eps_nodes, &next_nodes);
 	  if (BE (err != REG_NOERROR, 0))
 	    {
 	      re_node_set_free (&next_nodes);
@@ -3009,9 +3019,12 @@ check_arrival_add_next_nodes (mctx, str_idx, cur_nodes, next_nodes)
     {
       int naccepted = 0;
       int cur_node = cur_nodes->elems[cur_idx];
+#if defined DEBUG || defined RE_ENABLE_I18N
       re_token_type_t type = dfa->nodes[cur_node].type;
-      if (IS_EPSILON_NODE (type))
-	continue;
+#endif
+#ifdef DEBUG
+      assert (!IS_EPSILON_NODE (type));
+#endif
 #ifdef RE_ENABLE_I18N
       /* If the node may accept `multi byte'.  */
       if (ACCEPT_MB_NODE (type))
@@ -3988,24 +4001,20 @@ check_node_accept (mctx, node, idx)
     const re_token_t *node;
     int idx;
 {
-  re_dfa_t *const dfa = mctx->dfa;
   unsigned char ch;
-  if (node->constraint)
-    {
-      /* The node has constraints.  Check whether the current context
-	 satisfies the constraints.  */
-      unsigned int context = re_string_context_at (&mctx->input, idx,
-						   mctx->eflags);
-      if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
-	return 0;
-    }
   ch = re_string_byte_at (&mctx->input, idx);
   switch (node->type)
     {
     case CHARACTER:
-      return node->opr.c == ch;
+      if (node->opr.c != ch)
+        return 0;
+      break;
+
     case SIMPLE_BRACKET:
-      return bitset_contain (node->opr.sbcset, ch);
+      if (!bitset_contain (node->opr.sbcset, ch))
+        return 0;
+      break;
+
 #ifdef RE_ENABLE_I18N
     case OP_UTF8_PERIOD:
       if (ch >= 0x80)
@@ -4013,11 +4022,26 @@ check_node_accept (mctx, node, idx)
       /* FALLTHROUGH */
 #endif
     case OP_PERIOD:
-      return !((ch == '\n' && !(dfa->syntax & RE_DOT_NEWLINE))
-	       || (ch == '\0' && (dfa->syntax & RE_DOT_NOT_NULL)));
+      if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
+	  || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
+	return 0;
+      break;
+
     default:
       return 0;
     }
+
+  if (node->constraint)
+    {
+      /* The node has constraints.  Check whether the current context
+	 satisfies the constraints.  */
+      unsigned int context = re_string_context_at (&mctx->input, idx,
+						   mctx->eflags);
+      if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
+	return 0;
+    }
+
+  return 1;
 }
 
 /* Extend the buffers, if the buffers have run out.  */