[PATCH] Fix #27777 - now use a doubly-linked list for _IO_list_all

[alexandre.ferrieux@orange.com]

From: Alexandre Ferrieux <alexandre.ferrieux@orange.com>

Hi,

This patch fixes #27777 "fclose does a linear search, takes ages when many FILE* are opened".
Simply put, the master list of opened (FILE*), namely _IO_list_all, is a singly-linked list.
As a consequence, the removal of a single element is in O(N), which cripples the performance
of fopen(). The patch switches to a doubly-linked list, yielding O(1) removal.

As an illustration, after opening 1 million (FILE*), the fclose() of 100 of them takes more
than 6 seconds without the patch, and under a millisecond with it.

Signed-off-by: Alexandre Ferrieux <alexandre.ferrieux@orange.com>


---
 elf/libc_early_init.c          |  3 +++
 libio/bits/types/struct_FILE.h |  2 +-
 libio/genops.c                 | 19 +++++++++----------
 libio/libioP.h                 | 11 +++++++----
 libio/stdfiles.c               |  8 ++++++++
 5 files changed, 28 insertions(+), 15 deletions(-)

diff --git a/elf/libc_early_init.c b/elf/libc_early_init.c
index 575b837f8f..756274f652 100644
--- a/elf/libc_early_init.c
+++ b/elf/libc_early_init.c
@@ -23,6 +23,7 @@
 #include <lowlevellock.h>
 #include <pthread_early_init.h>
 #include <sys/single_threaded.h>
+#include <libioP.h>
 
 #ifdef SHARED
 _Bool __libc_initial;
@@ -41,6 +42,8 @@ __libc_early_init (_Bool initial)
   __libc_single_threaded_internal = __libc_initial = initial;
 #endif
 
+  __stdfiles_init ();
+
   __pthread_early_init ();
 
 #if ENABLE_ELISION_SUPPORT
diff --git a/libio/bits/types/struct_FILE.h b/libio/bits/types/struct_FILE.h
index 7cdaae86f8..daebd6ce0a 100644
--- a/libio/bits/types/struct_FILE.h
+++ b/libio/bits/types/struct_FILE.h
@@ -67,7 +67,7 @@ struct _IO_FILE
 
   struct _IO_marker *_markers;
 
-  struct _IO_FILE *_chain;
+  struct _IO_FILE *_chain,**_prevchain;
 
   int _fileno;
   int _flags2;
diff --git a/libio/genops.c b/libio/genops.c
index bc45e60a09..a27f65581b 100644
--- a/libio/genops.c
+++ b/libio/genops.c
@@ -53,7 +53,6 @@ _IO_un_link (struct _IO_FILE_plus *fp)
 {
   if (fp->file._flags & _IO_LINKED)
     {
-      FILE **f;
 #ifdef _IO_MTSAFE_IO
       _IO_cleanup_region_start_noarg (flush_cleanup);
       _IO_lock_lock (list_all_lock);
@@ -62,15 +61,13 @@ _IO_un_link (struct _IO_FILE_plus *fp)
 #endif
       if (_IO_list_all == NULL)
 	;
-      else if (fp == _IO_list_all)
-	_IO_list_all = (struct _IO_FILE_plus *) _IO_list_all->file._chain;
-      else
-	for (f = &_IO_list_all->file._chain; *f; f = &(*f)->_chain)
-	  if (*f == (FILE *) fp)
-	    {
-	      *f = fp->file._chain;
-	      break;
-	    }
+      else {
+	struct _IO_FILE_plus **pr,*nx;
+	pr=(struct _IO_FILE_plus**)fp->file._prevchain;
+	nx=(struct _IO_FILE_plus*)fp->file._chain;
+	*pr=nx;
+	if (nx) nx->file._prevchain=(FILE **)pr;
+      }
       fp->file._flags &= ~_IO_LINKED;
 #ifdef _IO_MTSAFE_IO
       _IO_funlockfile ((FILE *) fp);
@@ -95,6 +92,8 @@ _IO_link_in (struct _IO_FILE_plus *fp)
       _IO_flockfile ((FILE *) fp);
 #endif
       fp->file._chain = (FILE *) _IO_list_all;
+      fp->file._prevchain = (FILE **) &_IO_list_all;
+      _IO_list_all->file._prevchain=&fp->file._chain;
       _IO_list_all = fp;
 #ifdef _IO_MTSAFE_IO
       _IO_funlockfile ((FILE *) fp);
diff --git a/libio/libioP.h b/libio/libioP.h
index 1af287b19f..5862f815bc 100644
--- a/libio/libioP.h
+++ b/libio/libioP.h
@@ -429,6 +429,9 @@ libc_hidden_proto (_IO_list_resetlock)
 extern void _IO_enable_locks (void) __THROW;
 libc_hidden_proto (_IO_enable_locks)
 
+/* Needed for proper initialization of the doubly-linked list */  
+extern void __stdfiles_init(void);
+
 /* Default jumptable functions. */
 
 extern int _IO_default_underflow (FILE *) __THROW;
@@ -904,12 +907,12 @@ extern int _IO_vscanf (const char *, va_list) __THROW;
 # ifdef _IO_USE_OLD_IO_FILE
 #  define FILEBUF_LITERAL(CHAIN, FLAGS, FD, WDP) \
        { _IO_MAGIC+_IO_LINKED+_IO_IS_FILEBUF+FLAGS, \
-	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, FD, \
+	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, NULL, FD,	\
 	 0, _IO_pos_BAD, 0, 0, { 0 }, &_IO_stdfile_##FD##_lock }
 # else
 #  define FILEBUF_LITERAL(CHAIN, FLAGS, FD, WDP) \
        { _IO_MAGIC+_IO_LINKED+_IO_IS_FILEBUF+FLAGS, \
-	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, FD, \
+	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, NULL, FD,	\
 	 0, _IO_pos_BAD, 0, 0, { 0 }, &_IO_stdfile_##FD##_lock, _IO_pos_BAD,\
 	 NULL, WDP, 0 }
 # endif
@@ -917,12 +920,12 @@ extern int _IO_vscanf (const char *, va_list) __THROW;
 # ifdef _IO_USE_OLD_IO_FILE
 #  define FILEBUF_LITERAL(CHAIN, FLAGS, FD, WDP) \
        { _IO_MAGIC+_IO_LINKED+_IO_IS_FILEBUF+FLAGS, \
-	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, FD, \
+	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, NULL, FD,	\
 	 0, _IO_pos_BAD }
 # else
 #  define FILEBUF_LITERAL(CHAIN, FLAGS, FD, WDP) \
        { _IO_MAGIC+_IO_LINKED+_IO_IS_FILEBUF+FLAGS, \
-	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, FD, \
+	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, NULL, FD,	\
 	 0, _IO_pos_BAD, 0, 0, { 0 }, 0, _IO_pos_BAD, \
 	 NULL, WDP, 0 }
 # endif
diff --git a/libio/stdfiles.c b/libio/stdfiles.c
index cd8eca8bf3..87c9b249df 100644
--- a/libio/stdfiles.c
+++ b/libio/stdfiles.c
@@ -54,4 +54,12 @@ DEF_STDFILE(_IO_2_1_stdout_, 1, &_IO_2_1_stdin_, _IO_NO_READS);
 DEF_STDFILE(_IO_2_1_stderr_, 2, &_IO_2_1_stdout_, _IO_NO_READS+_IO_UNBUFFERED);
 
 struct _IO_FILE_plus *_IO_list_all = &_IO_2_1_stderr_;
+
+void __stdfiles_init(void) // finish the double-linking for stdfiles as static initialization cannot
+{
+  struct _IO_FILE **f;
+
+  for(f=(struct _IO_FILE **)&_IO_list_all;(*f);f=&(**f)._chain) (**f)._prevchain=f;
+}
+
 libc_hidden_data_def (_IO_list_all)
-- 
2.30.2

____________________________________________________________________________________________________________
Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.