Use a doubly-linked list for _IO_list_all (bug 27777)

This patch fixes BZ #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 fclose().  The patch switches to a doubly-linked list, yielding O(1)
removal.  The one padding field in struct _IO_FILE, __pad5, is renamed
to _prevchain for a doubly-linked list.  Since fields in struct _IO_FILE
after the _lock field are internal to glibc and opaque to applications.
We can change them as long as the size of struct _IO_FILE is unchanged,
which is checked as the part of glibc ABI with sizes of _IO_2_1_stdin_,
_IO_2_1_stdout_ and _IO_2_1_stderr_.

NB: When _IO_vtable_offset (fp) == 0, copy relocation will cover the
whole struct _IO_FILE.  Otherwise, only fields up to the _lock field
will be copied to applications at run-time.  It is used to check if
the _prevchain field can be safely accessed.

After opening 2 million (FILE*), the fclose() of 100 of them takes quite
a few seconds without the patch, and under 2 seconds with it on a loaded
machine.

No test is added since there are no functional changes.

Co-Authored-By: H.J. Lu <hjl.tools@gmail.com>
Signed-off-by: Alexandre Ferrieux <alexandre.ferrieux@orange.com>
Signed-off-by: H.J. Lu <hjl.tools@gmail.com>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>

1 files changed, 26 insertions, 0 deletions

diff --git a/libio/genops.c b/libio/genops.c
index bc45e60a09..994ee9c0b1 100644
--- a/libio/genops.c
+++ b/libio/genops.c
@@ -48,6 +48,19 @@ flush_cleanup (void *not_used)
 }
 #endif
 
+/* Fields in struct _IO_FILE after the _lock field are internal to
+   glibc and opaque to applications.  We can change them as long as
+   the size of struct _IO_FILE is unchanged, which is checked as the
+   part of glibc ABI with sizes of _IO_2_1_stdin_, _IO_2_1_stdout_
+   and _IO_2_1_stderr_.
+
+   NB: When _IO_vtable_offset (fp) == 0, copy relocation will cover the
+   whole struct _IO_FILE.  Otherwise, only fields up to the _lock field
+   will be copied.  */
+_Static_assert (offsetof (struct _IO_FILE, _prevchain)
+		> offsetof (struct _IO_FILE, _lock),
+		"offset of _prevchain > offset of _lock");
+
 void
 _IO_un_link (struct _IO_FILE_plus *fp)
 {
@@ -62,6 +75,14 @@ _IO_un_link (struct _IO_FILE_plus *fp)
 #endif
       if (_IO_list_all == NULL)
 	;
+      else if (_IO_vtable_offset ((FILE *) fp) == 0)
+	{
+	  FILE **pr = fp->file._prevchain;
+	  FILE *nx = fp->file._chain;
+	  *pr = nx;
+	  if (nx != NULL)
+	    nx->_prevchain = pr;
+	}
       else if (fp == _IO_list_all)
 	_IO_list_all = (struct _IO_FILE_plus *) _IO_list_all->file._chain;
       else
@@ -95,6 +116,11 @@ _IO_link_in (struct _IO_FILE_plus *fp)
       _IO_flockfile ((FILE *) fp);
 #endif
       fp->file._chain = (FILE *) _IO_list_all;
+      if (_IO_vtable_offset ((FILE *) fp) == 0)
+	{
+	  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);