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

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

[alexandre.ferrieux]

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.

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

[H.J. Lu]

On Fri, Apr 26, 2024 at 7:19 AM <alexandre.ferrieux@orange.com> wrote:
>
> 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;

We need to add a new symbol version for stdio functions
when FILE size is changed.

>    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.
>


-- 
H.J.

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

[H.J. Lu]

On Fri, Apr 26, 2024 at 8:02 AM <alexandre.ferrieux@orange.com> wrote:
>
> On 26/04/2024 16:45, H.J. Lu wrote:
> >
> >> -  struct _IO_FILE *_chain;
> >> +  struct _IO_FILE *_chain,**_prevchain;
> >
> > We need to add a new symbol version for stdio functions
> > when FILE size is changed.
>
> Is there a README introducing newcomers (like me) to the shenanigans of symvers,
> the rules chosen for libc and their rationale ?

Please do "git grep COMPAT libio" for stdio symbol version examples.

> Otherwise, it looks like you'll be way faster than me to do it. Be my guest.
>


-- 
H.J.

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

[H.J. Lu]

On Fri, Apr 26, 2024 at 8:05 AM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Fri, Apr 26, 2024 at 8:02 AM <alexandre.ferrieux@orange.com> wrote:
> >
> > On 26/04/2024 16:45, H.J. Lu wrote:
> > >
> > >> -  struct _IO_FILE *_chain;
> > >> +  struct _IO_FILE *_chain,**_prevchain;

When expanding FILE, the new field should be placed at the end
so that the compat stdio functions can work properly.

> > >
> > > We need to add a new symbol version for stdio functions
> > > when FILE size is changed.
> >
> > Is there a README introducing newcomers (like me) to the shenanigans of symvers,
> > the rules chosen for libc and their rationale ?
>
> Please do "git grep COMPAT libio" for stdio symbol version examples.
>
> > Otherwise, it looks like you'll be way faster than me to do it. Be my guest.
> >
>
>
> --
> H.J.



-- 
H.J.

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

[H.J. Lu]

On Fri, Apr 26, 2024 at 8:13 AM <alexandre.ferrieux@orange.com> wrote:
>
> On 26/04/2024 17:05, H.J. Lu wrote:
> > --------------------------------------------------------------------------------------------------------------
> > CAUTION : This email originated outside the company. Do not click on any links or open attachments unless you are expecting them from the sender.
> >
> > ATTENTION : Cet e-mail provient de l'extérieur de l'entreprise. Ne cliquez pas sur les liens ou n'ouvrez pas les pièces jointes à moins de connaitre l'expéditeur.
> > --------------------------------------------------------------------------------------------------------------
> >
> > On Fri, Apr 26, 2024 at 8:02 AM <alexandre.ferrieux@orange.com> wrote:
> >>
> >> On 26/04/2024 16:45, H.J. Lu wrote:
> >> >
> >> >> -  struct _IO_FILE *_chain;
> >> >> +  struct _IO_FILE *_chain,**_prevchain;
> >> >
> >> > We need to add a new symbol version for stdio functions
> >> > when FILE size is changed.
> >>
> >> Is there a README introducing newcomers (like me) to the shenanigans of symvers,
> >> the rules chosen for libc and their rationale ?
> >
> > Please do "git grep COMPAT libio" for stdio symbol version examples.
>
> Sorry, I won't guess from examples. Rules and rationale, anybody ?

It is very straightforward. The binaries compiled against the old FILE
must work correctly with the new glibc.

-- 
H.J.

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

[H.J. Lu]

[-- Attachment #1: Type: text/plain, Size: 1322 bytes --]

On Fri, Apr 26, 2024 at 8:19 AM <alexandre.ferrieux@orange.com> wrote:
>
>
>
> On 26/04/2024 17:16, H.J. Lu wrote:
> >
> > On Fri, Apr 26, 2024 at 8:13 AM <alexandre.ferrieux@orange.com> wrote:
> >>
> >> On 26/04/2024 17:05, H.J. Lu wrote:
> >> >
> >> > On Fri, Apr 26, 2024 at 8:02 AM <alexandre.ferrieux@orange.com> wrote:
> >> >>
> >> >> On 26/04/2024 16:45, H.J. Lu wrote:
> >> >> >
> >> >> >> -  struct _IO_FILE *_chain;
> >> >> >> +  struct _IO_FILE *_chain,**_prevchain;
> >> >> >
> >> >> > We need to add a new symbol version for stdio functions
> >> >> > when FILE size is changed.
> >> >>
> >> >> Is there a README introducing newcomers (like me) to the shenanigans of symvers,
> >> >> the rules chosen for libc and their rationale ?
> >> >
> >> > Please do "git grep COMPAT libio" for stdio symbol version examples.
> >>
> >> Sorry, I won't guess from examples. Rules and rationale, anybody ?
> >
> > It is very straightforward. The binaries compiled against the old FILE
> > must work correctly with the new glibc.
>
> I had the naive assumption that FILE was an opaque type for libc users.
> Is it wrong ? See why a rationale document is needed ?

I updated your patch with a new version.  _IO_un_link@@GLIBC_2.40
must be added to all libc.abilist files.

-- 
H.J.

[-- Attachment #2: 0001-Fix-27777-now-use-a-doubly-linked-list-for-_IO_list_.patch --]
[-- Type: text/x-patch, Size: 7442 bytes --]

From 961d92d314442b502a7af26fb84860429a2aa9ca Mon Sep 17 00:00:00 2001
From: Alexandre Ferrieux <alexandre.ferrieux@orange.com>
Date: Fri, 26 Apr 2024 16:18:47 +0200
Subject: [PATCH] Fix #27777 - now use a doubly-linked list for _IO_list_all

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/Versions                 |  4 +++
 libio/bits/types/struct_FILE.h |  4 ++-
 libio/genops.c                 | 62 ++++++++++++++++++++++++++++------
 libio/libioP.h                 |  7 ++--
 libio/stdfiles.c               | 15 ++++++++
 6 files changed, 81 insertions(+), 14 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/Versions b/libio/Versions
index b91a7bc914..87f24e323a 100644
--- a/libio/Versions
+++ b/libio/Versions
@@ -155,6 +155,10 @@ libc {
     # f*
     fmemopen;
   }
+  GLIBC_2.40 {
+    # libio
+    _IO_un_link;
+  }
   GLIBC_PRIVATE {
     # Used by NPTL and librt
     __libc_fatal;
diff --git a/libio/bits/types/struct_FILE.h b/libio/bits/types/struct_FILE.h
index 7cdaae86f8..b1cb01746f 100644
--- a/libio/bits/types/struct_FILE.h
+++ b/libio/bits/types/struct_FILE.h
@@ -94,8 +94,10 @@ struct _IO_FILE_complete
   void *_freeres_buf;
   size_t __pad5;
   int _mode;
+  struct _IO_FILE **_prevchain;
   /* Make sure we don't get into trouble again.  */
-  char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
+  char _unused2[15 * sizeof (int) - 4 * sizeof (void *)
+		- sizeof (size_t) - sizeof (struct _IO_FILE **)];
 };
 
 /* These macros are used by bits/stdio.h and internal headers.  */
diff --git a/libio/genops.c b/libio/genops.c
index bc45e60a09..5f561084a2 100644
--- a/libio/genops.c
+++ b/libio/genops.c
@@ -31,6 +31,7 @@
 #include <string.h>
 #include <stdbool.h>
 #include <sched.h>
+#include <shlib-compat.h>
 
 #ifdef _IO_MTSAFE_IO
 static _IO_lock_t list_all_lock = _IO_lock_initializer;
@@ -49,11 +50,10 @@ flush_cleanup (void *not_used)
 #endif
 
 void
-_IO_un_link (struct _IO_FILE_plus *fp)
+_new_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 +62,15 @@ _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;
-	    }
+	{
+	  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 != NULL)
+	    nx->file._prevchain = (FILE **) pr;
+	}
       fp->file._flags &= ~_IO_LINKED;
 #ifdef _IO_MTSAFE_IO
       _IO_funlockfile ((FILE *) fp);
@@ -80,7 +80,8 @@ _IO_un_link (struct _IO_FILE_plus *fp)
 #endif
     }
 }
-libc_hidden_def (_IO_un_link)
+libc_hidden_ver (_new_IO_un_link, _IO_un_link)
+versioned_symbol (libc, _new_IO_un_link, _IO_un_link, GLIBC_2_40);
 
 void
 _IO_link_in (struct _IO_FILE_plus *fp)
@@ -95,6 +96,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);
@@ -1092,3 +1095,40 @@ _IO_list_resetlock (void)
 #endif
 }
 libc_hidden_def (_IO_list_resetlock)
+
+#if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_40)
+
+void
+_old_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);
+      run_fp = (FILE *) fp;
+      _IO_flockfile ((FILE *) 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;
+	    }
+      fp->file._flags &= ~_IO_LINKED;
+#ifdef _IO_MTSAFE_IO
+      _IO_funlockfile ((FILE *) fp);
+      run_fp = NULL;
+      _IO_lock_unlock (list_all_lock);
+      _IO_cleanup_region_end (0);
+#endif
+    }
+}
+compat_symbol (libc, _old_IO_un_link, _IO_un_link, GLIBC_2_0);
+#endif
diff --git a/libio/libioP.h b/libio/libioP.h
index 1af287b19f..3d642c04ed 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) attribute_hidden;
+
 /* Default jumptable functions. */
 
 extern int _IO_default_underflow (FILE *) __THROW;
@@ -911,7 +914,7 @@ extern int _IO_vscanf (const char *, va_list) __THROW;
        { _IO_MAGIC+_IO_LINKED+_IO_IS_FILEBUF+FLAGS, \
 	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, FD, \
 	 0, _IO_pos_BAD, 0, 0, { 0 }, &_IO_stdfile_##FD##_lock, _IO_pos_BAD,\
-	 NULL, WDP, 0 }
+	 NULL, WDP, 0, NULL }
 # endif
 #else
 # ifdef _IO_USE_OLD_IO_FILE
@@ -924,7 +927,7 @@ extern int _IO_vscanf (const char *, va_list) __THROW;
        { _IO_MAGIC+_IO_LINKED+_IO_IS_FILEBUF+FLAGS, \
 	 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (FILE *) CHAIN, FD, \
 	 0, _IO_pos_BAD, 0, 0, { 0 }, 0, _IO_pos_BAD, \
-	 NULL, WDP, 0 }
+	 NULL, WDP, 0, NULL }
 # endif
 #endif
 
diff --git a/libio/stdfiles.c b/libio/stdfiles.c
index cd8eca8bf3..f10d2688cb 100644
--- a/libio/stdfiles.c
+++ b/libio/stdfiles.c
@@ -54,4 +54,19 @@ 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_;
+
+/* Finish the double-linking for stdfiles as static initialization
+   cannot.  */
+
+void
+__stdfiles_init (void)
+{
+  struct _IO_FILE **f;
+
+  for (f = (struct _IO_FILE **) &_IO_list_all;
+       *f != NULL;
+       f = &(**f)._chain)
+    (**f)._prevchain = f;
+}
+
 libc_hidden_data_def (_IO_list_all)
-- 
2.44.0

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

[H.J. Lu]

On Fri, Apr 26, 2024 at 9:21 AM <alexandre.ferrieux@orange.com> wrote:
>
>
>
> On 26/04/2024 18:08, H.J. Lu wrote:
> >> >> >> >
> >> >> >> >> -  struct _IO_FILE *_chain;
> >> >> >> >> +  struct _IO_FILE *_chain,**_prevchain;
> >> >> >> >
> >> >> >> > We need to add a new symbol version for stdio functions
> >> >> >> > when FILE size is changed.
> >> >> >>
> >> >> >> Is there a README introducing newcomers (like me) to the shenanigans of symvers,
> >> >> >> the rules chosen for libc and their rationale ?
> >> >> >
> >> >> > Please do "git grep COMPAT libio" for stdio symbol version examples.
> >> >>
> >> >> Sorry, I won't guess from examples. Rules and rationale, anybody ?
> >> >
> >> > It is very straightforward. The binaries compiled against the old FILE
> >> > must work correctly with the new glibc.
> >>
> >> I had the naive assumption that FILE was an opaque type for libc users.
> >> Is it wrong ? See why a rationale document is needed ?
> >
> > I updated your patch with a new version.  _IO_un_link@@GLIBC_2.40
> > must be added to all libc.abilist files.
>
>
> Thanks a lot.
> But why is only _IO_un_link concerned by this versioning, and not also _IO_link_in ?
>

Yes, _IO_link_in also needs a new version.

-- 
H.J.

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

[Florian Weimer]

* alexandre ferrieux:

> 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;

Unfortunately, this struct is part of the ABI for several reasons.  For
example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
it has a struct _IO_FILE member.  It cannot change size due to copy
relocations, even if nothing accesses members after _chain.

I disagree with H.J.'s suggestion that the answer is symbol
versions. 8-)

Two options come to my mind: Use the FILE * value itself as a hash table
key (and use _chain for resolving bucket conflicts), or use a dynarray
and replace _chain with a union of a pointer and an unsigned int,
containing the dynarray index for that particular file.  The latter has
the advantage that we can use it to implement arbitrary extensions in
the future.  Either approach should preserve compatibility with GCC 2.95
libstdc++ if we are a bit careful.

Historically, we used a single-linked list here because we wanted to
traverse it without locking, but we are no longer doing that, so we can
pick any data structure we want instead.

Thanks,
Florian

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

[alexandre.ferrieux]

On 26/04/2024 19:51, Florian Weimer wrote:
> 
> * alexandre ferrieux:
> 
>> 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;
> 
> Unfortunately, this struct is part of the ABI for several reasons.  For
> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
> it has a struct _IO_FILE member.  It cannot change size due to copy
> relocations, even if nothing accesses members after _chain.
> 
> I disagree with H.J.'s suggestion that the answer is symbol
> versions. 8-)

Interesting !

So we are in the presence of software that can no longer change, _ever_ ?
What about bumping to _IO_2_2 ?

> Two options come to my mind: Use the FILE * value itself as a hash table
> key (and use _chain for resolving bucket conflicts), or use a dynarray
> and replace _chain with a union of a pointer and an unsigned int,
> containing the dynarray index for that particular file.  The latter has
> the advantage that we can use it to implement arbitrary extensions in
> the future.  Either approach should preserve compatibility with GCC 2.95
> libstdc++ if we are a bit careful.

Argggh. Jumping through complex, inefficient and hard-to-maintain hoops,
because a fundamentally opaque type has been inadvertently exposed ?

Imagine the state of _IO_FILE 50 years from now, after a dozen of similar hacks 
have piled up...

Are there absolutely no plans to someday deprecate the problematic, but 
extremely rare, accesses to those types that should have remained opaque ?



____________________________________________________________________________________________________________
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.

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

[alexandre.ferrieux]

On 26/04/2024 20:20, FERRIEUX Alexandre INNOV/NET wrote:
> 
> 
> On 26/04/2024 19:51, Florian Weimer wrote:
>>
>> * alexandre ferrieux:
>>
>>> 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;
>>
>> Unfortunately, this struct is part of the ABI for several reasons.  For
>> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
>> it has a struct _IO_FILE member.  It cannot change size due to copy
>> relocations, even if nothing accesses members after _chain.

Now what about sticking the field to the end of _IO_FILE_plus ?

  struct _IO_FILE_plus
  {
    FILE file;
    const struct _IO_jump_t *vtable;
+  struct _IO_FILE_plus **_prevchain;
  };

Wouldn't that be backwards compatible with everything ?
Or do you suspect that some aircraft, dams and power plants routinely rely on 
sizeof(_IO_FILE_plus) as they allocate and fill their file pointers by hand ?
____________________________________________________________________________________________________________
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.

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

[H.J. Lu]

On Fri, Apr 26, 2024 at 10:51 AM Florian Weimer <fweimer@redhat.com> wrote:
>
> * alexandre ferrieux:
>
> > 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;
>
> Unfortunately, this struct is part of the ABI for several reasons.  For
> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
> it has a struct _IO_FILE member.  It cannot change size due to copy
> relocations, even if nothing accesses members after _chain.
>
> I disagree with H.J.'s suggestion that the answer is symbol
> versions. 8-)

libio/bits/types/struct_FILE.h has

  __off64_t _offset;
  /* Wide character stream stuff.  */
  struct _IO_codecvt *_codecvt;
  struct _IO_wide_data *_wide_data;
  struct _IO_FILE *_freeres_list;
  void *_freeres_buf;
  size_t __pad5;
  int _mode;
  /* Make sure we don't get into trouble again.  */
  char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
};

We can add a pointer without changing FILE size.

> Two options come to my mind: Use the FILE * value itself as a hash table
> key (and use _chain for resolving bucket conflicts), or use a dynarray
> and replace _chain with a union of a pointer and an unsigned int,
> containing the dynarray index for that particular file.  The latter has
> the advantage that we can use it to implement arbitrary extensions in
> the future.  Either approach should preserve compatibility with GCC 2.95
> libstdc++ if we are a bit careful.
>
> Historically, we used a single-linked list here because we wanted to
> traverse it without locking, but we are no longer doing that, so we can
> pick any data structure we want instead.
>
> Thanks,
> Florian
>


-- 
H.J.

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

[alexandre.ferrieux]

On 26/04/2024 20:50, H.J. Lu wrote:
>
> On Fri, Apr 26, 2024 at 10:51 AM Florian Weimer <fweimer@redhat.com> wrote:
>>
>> * alexandre ferrieux:
>>
>> > 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;
>>
>> Unfortunately, this struct is part of the ABI for several reasons.  For
>> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
>> it has a struct _IO_FILE member.  It cannot change size due to copy
>> relocations, even if nothing accesses members after _chain.
>>
>> I disagree with H.J.'s suggestion that the answer is symbol
>> versions. 8-)
> 
> libio/bits/types/struct_FILE.h has
> 
>    __off64_t _offset;
>    /* Wide character stream stuff.  */
>    struct _IO_codecvt *_codecvt;
>    struct _IO_wide_data *_wide_data;
>    struct _IO_FILE *_freeres_list;
>    void *_freeres_buf;
>    size_t __pad5;
>    int _mode;
>    /* Make sure we don't get into trouble again.  */
>    char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
> };
> 
> We can add a pointer without changing FILE size.

Ha ! That's a clever trick. Presumably someone was already bitten once ;)
(Sorry I didn't notice it was present in your corrected patch).

Now, I still have worries about the symbol versioning approach: why restrict the 
version bump to _IO_un_link and _IO_link_in ? Indeed, any program calling 
fclose()  ends up calling _IO_un_link(), so the version check should apply too, 
right ? So shouldn't we tag all functions using (FILE *) in their arguments or 
return value ?
____________________________________________________________________________________________________________
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.

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

[Florian Weimer]

* alexandre ferrieux:

> On 26/04/2024 19:51, Florian Weimer wrote:
>> * alexandre ferrieux:
>> 
>>> 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;
>> Unfortunately, this struct is part of the ABI for several reasons.
>> For
>> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
>> it has a struct _IO_FILE member.  It cannot change size due to copy
>> relocations, even if nothing accesses members after _chain.
>> I disagree with H.J.'s suggestion that the answer is symbol
>> versions. 8-)
>
> Interesting !
>
> So we are in the presence of software that can no longer change, _ever_ ?
> What about bumping to _IO_2_2 ?

That requires specific code paths to deal with the earlier versions.

>> Two options come to my mind: Use the FILE * value itself as a hash table
>> key (and use _chain for resolving bucket conflicts), or use a dynarray
>> and replace _chain with a union of a pointer and an unsigned int,
>> containing the dynarray index for that particular file.  The latter has
>> the advantage that we can use it to implement arbitrary extensions in
>> the future.  Either approach should preserve compatibility with GCC 2.95
>> libstdc++ if we are a bit careful.
>
> Argggh. Jumping through complex, inefficient and hard-to-maintain hoops,
> because a fundamentally opaque type has been inadvertently exposed ?

The approaches I mention have the advantage that they work for both
glibc 2.0 and glibc 2.1 (current) file streams, using the same code,
which simplifies testing.

If you want to work on hiding the internals of struct _IO_FILE, that
would be very welcome, but it's a much larger project than fixing this
particular performance issue.

Thanks,
Florian

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

[Florian Weimer]

* alexandre ferrieux:

> On 26/04/2024 20:20, FERRIEUX Alexandre INNOV/NET wrote:
>> On 26/04/2024 19:51, Florian Weimer wrote:
>>>
>>> * alexandre ferrieux:
>>>
>>>> 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;
>>>
>>> Unfortunately, this struct is part of the ABI for several reasons.  For
>>> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
>>> it has a struct _IO_FILE member.  It cannot change size due to copy
>>> relocations, even if nothing accesses members after _chain.
>
> Now what about sticking the field to the end of _IO_FILE_plus ?
>
>  struct _IO_FILE_plus
>  {
>    FILE file;
>    const struct _IO_jump_t *vtable;
> +  struct _IO_FILE_plus **_prevchain;
>  };
>
> Wouldn't that be backwards compatible with everything ?

Sorry, no, struct _IO_FILE_plus is used to define _IO_2_1_stdin_.

Florian

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

[Florian Weimer]

* H. J. Lu:

> On Fri, Apr 26, 2024 at 10:51 AM Florian Weimer <fweimer@redhat.com> wrote:
>>
>> * alexandre ferrieux:
>>
>> > 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;
>>
>> Unfortunately, this struct is part of the ABI for several reasons.  For
>> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
>> it has a struct _IO_FILE member.  It cannot change size due to copy
>> relocations, even if nothing accesses members after _chain.
>>
>> I disagree with H.J.'s suggestion that the answer is symbol
>> versions. 8-)
>
> libio/bits/types/struct_FILE.h has
>
>   __off64_t _offset;
>   /* Wide character stream stuff.  */
>   struct _IO_codecvt *_codecvt;
>   struct _IO_wide_data *_wide_data;
>   struct _IO_FILE *_freeres_list;
>   void *_freeres_buf;
>   size_t __pad5;
>   int _mode;
>   /* Make sure we don't get into trouble again.  */
>   char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
> };
>
> We can add a pointer without changing FILE size.

Indeed, but that still needs special-cases for glibc 2.0 file handles,
which do not necessarily have the extended tail.  Maybe it's possible to
make the backlink processing optional for glibc 2.0 targets.

Thanks,
Florian

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

[Florian Weimer]

* alexandre ferrieux:

> On 26/04/2024 20:50, H.J. Lu wrote:
>>
>> On Fri, Apr 26, 2024 at 10:51 AM Florian Weimer <fweimer@redhat.com> wrote:
>>>
>>> * alexandre ferrieux:
>>>
>>> > 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;
>>>
>>> Unfortunately, this struct is part of the ABI for several reasons.  For
>>> example, _IO_2_1_stdin_ is a global variable exported by libc.so.6, and
>>> it has a struct _IO_FILE member.  It cannot change size due to copy
>>> relocations, even if nothing accesses members after _chain.
>>>
>>> I disagree with H.J.'s suggestion that the answer is symbol
>>> versions. 8-)
>> libio/bits/types/struct_FILE.h has
>>    __off64_t _offset;
>>    /* Wide character stream stuff.  */
>>    struct _IO_codecvt *_codecvt;
>>    struct _IO_wide_data *_wide_data;
>>    struct _IO_FILE *_freeres_list;
>>    void *_freeres_buf;
>>    size_t __pad5;
>>    int _mode;
>>    /* Make sure we don't get into trouble again.  */
>>    char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
>> };
>> We can add a pointer without changing FILE size.
>
> Ha ! That's a clever trick. Presumably someone was already bitten once ;)
> (Sorry I didn't notice it was present in your corrected patch).
>
> Now, I still have worries about the symbol versioning approach: why
> restrict the version bump to _IO_un_link and _IO_link_in ? Indeed, any
> program calling fclose()  ends up calling _IO_un_link(), so the
> version check should apply too, right ? So shouldn't we tag all
> functions using (FILE *) in their arguments or return value ?

No new symbol versions should be needed.  You just need to be careful
not to access that part of the struct when it does not exist.

I think the way to check for old-style streams is via _IO_vtable_offset,
as can be seen at the start of the __fgetln function in an (unmerged)
patch I submitted a while back:

  [PATCH] stdio-common: Add the fgetln function
  <https://inbox.sourceware.org/libc-alpha/871qxbxe2i.fsf@oldenburg.str.redhat.com/>

In your case, you would have to do the full traversal once you encounter
a missing backlink.  But that would only happen if old-style file
handles are actually used.  Maybe this is even easier to implement than
the hash table or index approach.

Thanks,
Florian

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

[alexandre.ferrieux]

On 26/04/2024 21:16, Florian Weimer wrote:
> 
> * alexandre ferrieux:
> 
>> Now, I still have worries about the symbol versioning approach: why
>> restrict the version bump to _IO_un_link and _IO_link_in ? Indeed, any
>> program calling fclose()  ends up calling _IO_un_link(), so the
>> version check should apply too, right ? So shouldn't we tag all
>> functions using (FILE *) in their arguments or return value ?
> 
> No new symbol versions should be needed.  You just need to be careful
> not to access that part of the struct when it does not exist.
> 
> I think the way to check for old-style streams is via _IO_vtable_offset,
> as can be seen at the start of the __fgetln function in an (unmerged)
> patch I submitted a while back:
> 
>    [PATCH] stdio-common: Add the fgetln function
>    <https://inbox.sourceware.org/libc-alpha/871qxbxe2i.fsf@oldenburg.str.redhat.com/>
> 
> In your case, you would have to do the full traversal once you encounter
> a missing backlink.  But that would only happen if old-style file
> handles are actually used.  Maybe this is even easier to implement than
> the hash table or index approach.

Thanks for pointing me in the right direction. Now I see I need a runtime check 
for each individual file pointer on the list, as one cannot exclude a scenario 
where a (disgusting) old binary would malloc a decades-old variant of FILE, and 
stick it to the head of the list through an innocent _IO_link_in().

To do this in a robust manner, how about using _flags2 ?
(I see _flags has one value left, 0x4000, but it's "reserved for compat"... too bad)

Something like:

   #define _IO_FLAGS2_HAS_PREVCHAIN 256

   void 
 
 

   _IO_old_init (FILE *fp, int flags) 
 
 

   {
      ...
      fp->flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
   }

   void __stdfiles_init(void)
   {
      ...
      (**f).flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
   }


Then, (fp->flags2&_IO_FLAGS2_HAS_PREVCHAIN) becomes a reliable criterion for 
_IO_link_in and _IO_un_link to decide whether to use the new algorithm or the 
old one.

What do you think ?

____________________________________________________________________________________________________________
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.

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

[Florian Weimer]

* alexandre ferrieux:

> To do this in a robust manner, how about using _flags2 ?
> (I see _flags has one value left, 0x4000, but it's "reserved for compat"... too bad)
>
> Something like:
>
>   #define _IO_FLAGS2_HAS_PREVCHAIN 256
>
>   void      _IO_old_init (FILE *fp, int flags)      {
>      ...
>      fp->flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
>   }
>
>   void __stdfiles_init(void)
>   {
>      ...
>      (**f).flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
>   }
>
>
> Then, (fp->flags2&_IO_FLAGS2_HAS_PREVCHAIN) becomes a reliable
> criterion for _IO_link_in and _IO_un_link to decide whether to use the
> new algorithm or the old one.
>
> What do you think ?

I believe you can use the vtable_offset field as that flag.  See this
code in stdio-common/vfprintf-internal.c:

    133 
    134 # define ORIENT         if (_IO_vtable_offset (s) == 0 && _IO_fwide (s,
    134  -1) != -1)\
    135                           return -1

Thanks,
Florian

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

[alexandre.ferrieux]

On 29/04/2024 15:20, Florian Weimer wrote:
> 
> * alexandre ferrieux:
> 
>> To do this in a robust manner, how about using _flags2 ?
>> (I see _flags has one value left, 0x4000, but it's "reserved for compat"... too bad)
>>
>> Something like:
>>
>>   #define _IO_FLAGS2_HAS_PREVCHAIN 256
>>
>>   void      _IO_old_init (FILE *fp, int flags)      {
>>      ...
>>      fp->flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
>>   }
>>
>>   void __stdfiles_init(void)
>>   {
>>      ...
>>      (**f).flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
>>   }
>>
>>
>> Then, (fp->flags2&_IO_FLAGS2_HAS_PREVCHAIN) becomes a reliable
>> criterion for _IO_link_in and _IO_un_link to decide whether to use the
>> new algorithm or the old one.
>>
>> What do you think ?
> 
> I believe you can use the vtable_offset field as that flag.  See this
> code in stdio-common/vfprintf-internal.c:
> 
>      133
>      134 # define ORIENT         if (_IO_vtable_offset (s) == 0 && _IO_fwide (s,
>      134  -1) != -1)\
>      135                           return -1

Why is it sufficient ? Doesn't the nullity of the vtable_offset identify a 
different point in versions history ?

An "old binary", recent enough to have the modern vtable_offset, but compiled 
with the include files just before the patch, can presumably create an old 
_IO_FILE, insert it "by hand" into _IO_list_all, *not* updating the prevchain of 
the next-in-line, and then crash when the latter is closed.

____________________________________________________________________________________________________________
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.

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

[H.J. Lu]

[-- Attachment #1: Type: text/plain, Size: 1765 bytes --]

On Mon, Apr 29, 2024 at 12:05 PM <alexandre.ferrieux@orange.com> wrote:
>
> On 29/04/2024 15:20, Florian Weimer wrote:
> >
> > * alexandre ferrieux:
> >
> >> To do this in a robust manner, how about using _flags2 ?
> >> (I see _flags has one value left, 0x4000, but it's "reserved for compat"... too bad)
> >>
> >> Something like:
> >>
> >>   #define _IO_FLAGS2_HAS_PREVCHAIN 256
> >>
> >>   void      _IO_old_init (FILE *fp, int flags)      {
> >>      ...
> >>      fp->flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
> >>   }
> >>
> >>   void __stdfiles_init(void)
> >>   {
> >>      ...
> >>      (**f).flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
> >>   }
> >>
> >>
> >> Then, (fp->flags2&_IO_FLAGS2_HAS_PREVCHAIN) becomes a reliable

This won't work for copy relocation in old binaries.

> >> criterion for _IO_link_in and _IO_un_link to decide whether to use the
> >> new algorithm or the old one.
> >>
> >> What do you think ?
> >
> > I believe you can use the vtable_offset field as that flag.  See this
> > code in stdio-common/vfprintf-internal.c:
> >
> >      133
> >      134 # define ORIENT         if (_IO_vtable_offset (s) == 0 && _IO_fwide (s,
> >      134  -1) != -1)\
> >      135                           return -1
>
> Why is it sufficient ? Doesn't the nullity of the vtable_offset identify a
> different point in versions history ?
>
> An "old binary", recent enough to have the modern vtable_offset, but compiled
> with the include files just before the patch, can presumably create an old
> _IO_FILE, insert it "by hand" into _IO_list_all, *not* updating the prevchain of
> the next-in-line, and then crash when the latter is closed.
>

Here is a patch with _IO_vtable_offset (s) == 0 check.

-- 
H.J.

[-- Attachment #2: 0001-Fix-27777-now-use-a-doubly-linked-list-for-_IO_list_.patch --]
[-- Type: text/x-patch, Size: 5690 bytes --]

From 853aeb09c3ee2e19aa50f8e7e2b96918fcb8f1ee Mon Sep 17 00:00:00 2001
From: Alexandre Ferrieux <alexandre.ferrieux@orange.com>
Date: Fri, 26 Apr 2024 16:18:47 +0200
Subject: [PATCH] Fix #27777 - now use a doubly-linked list for _IO_list_all

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.

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.
---
 elf/libc_early_init.c          |  3 +++
 libio/bits/types/struct_FILE.h |  4 ++--
 libio/genops.c                 | 26 ++++++++++++++++++++++++++
 libio/libioP.h                 |  3 +++
 libio/stdfiles.c               | 14 ++++++++++++++
 5 files changed, 48 insertions(+), 2 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..d8d26639d1 100644
--- a/libio/bits/types/struct_FILE.h
+++ b/libio/bits/types/struct_FILE.h
@@ -92,10 +92,10 @@ struct _IO_FILE_complete
   struct _IO_wide_data *_wide_data;
   struct _IO_FILE *_freeres_list;
   void *_freeres_buf;
-  size_t __pad5;
+  struct _IO_FILE **_prevchain;
   int _mode;
   /* Make sure we don't get into trouble again.  */
-  char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
+  char _unused2[15 * sizeof (int) - 5 * sizeof (void *)];
 };
 
 /* These macros are used by bits/stdio.h and internal headers.  */
diff --git a/libio/genops.c b/libio/genops.c
index bc45e60a09..f2da0ac32b 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 (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 (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);
diff --git a/libio/libioP.h b/libio/libioP.h
index 1af287b19f..e47d45e1f7 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) attribute_hidden;
+
 /* Default jumptable functions. */
 
 extern int _IO_default_underflow (FILE *) __THROW;
diff --git a/libio/stdfiles.c b/libio/stdfiles.c
index cd8eca8bf3..5edb719372 100644
--- a/libio/stdfiles.c
+++ b/libio/stdfiles.c
@@ -54,4 +54,18 @@ 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_;
+
+/* Finish the double-linking for stdfiles as static initialization
+   cannot.  */
+
+void
+__stdfiles_init (void)
+{
+  struct _IO_FILE **f;
+  for (f = (struct _IO_FILE **) &_IO_list_all;
+       *f != NULL;
+       f = &(*f)->_chain)
+    (*f)->_prevchain = f;
+}
+
 libc_hidden_data_def (_IO_list_all)
-- 
2.44.0

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

[H.J. Lu]

On Mon, Apr 29, 2024 at 7:47 PM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Mon, Apr 29, 2024 at 12:05 PM <alexandre.ferrieux@orange.com> wrote:
> >
> > On 29/04/2024 15:20, Florian Weimer wrote:
> > >
> > > * alexandre ferrieux:
> > >
> > >> To do this in a robust manner, how about using _flags2 ?
> > >> (I see _flags has one value left, 0x4000, but it's "reserved for compat"... too bad)
> > >>
> > >> Something like:
> > >>
> > >>   #define _IO_FLAGS2_HAS_PREVCHAIN 256
> > >>
> > >>   void      _IO_old_init (FILE *fp, int flags)      {
> > >>      ...
> > >>      fp->flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
> > >>   }
> > >>
> > >>   void __stdfiles_init(void)
> > >>   {
> > >>      ...
> > >>      (**f).flags2 |= _IO_FLAGS2_HAS_PREVCHAIN ;
> > >>   }
> > >>
> > >>
> > >> Then, (fp->flags2&_IO_FLAGS2_HAS_PREVCHAIN) becomes a reliable
>
> This won't work for copy relocation in old binaries.
>
> > >> criterion for _IO_link_in and _IO_un_link to decide whether to use the
> > >> new algorithm or the old one.
> > >>
> > >> What do you think ?
> > >
> > > I believe you can use the vtable_offset field as that flag.  See this
> > > code in stdio-common/vfprintf-internal.c:
> > >
> > >      133
> > >      134 # define ORIENT         if (_IO_vtable_offset (s) == 0 && _IO_fwide (s,
> > >      134  -1) != -1)\
> > >      135                           return -1
> >
> > Why is it sufficient ? Doesn't the nullity of the vtable_offset identify a
> > different point in versions history ?
> >
> > An "old binary", recent enough to have the modern vtable_offset, but compiled
> > with the include files just before the patch, can presumably create an old
> > _IO_FILE, insert it "by hand" into _IO_list_all, *not* updating the prevchain of
> > the next-in-line, and then crash when the latter is closed.
> >
>
> Here is a patch with _IO_vtable_offset (s) == 0 check.
>

Here is the updated patch with a testcase:

https://patchwork.sourceware.org/project/glibc/list/?series=33314

-- 
H.J.

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

[H.J. Lu]

On Tue, Apr 30, 2024 at 12:52 PM <alexandre.ferrieux@orange.com> wrote:
>
>
>
> On 30/04/2024 20:11, H.J. Lu wrote:
> >>  > As tst-fclose.c shows, after opening 2 million (FILE*), the fclose() of
> >>  > 100 of them takes more than a few seconds without the patch, and under
> >>  > 2 seconds with it.
> >>
> >> Don't you mean "under 2 milliseconds" ? That's closer to what I see here.
> >
> > The timeout value in tst-fclose.c is in seconds.  I verified that if
> > the doubly-linked list wasn't used, tst-fclose failed with timeout.
>
> Ah, OK, you mean 2s is the threshold used in the automated test, makes sense.
> But to illustrate/explain, it is worth mentioning it actually drops to milliseconds.

It depends on if the wall clock is used.   On a heavily loaded machine, it
can take much more than a few milliseconds.

-- 
H.J.

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

[alexandre.ferrieux]

On 30/04/2024 20:11, H.J. Lu wrote:
>>  > As tst-fclose.c shows, after opening 2 million (FILE*), the fclose() of
>>  > 100 of them takes more than a few seconds without the patch, and under
>>  > 2 seconds with it.
>>
>> Don't you mean "under 2 milliseconds" ? That's closer to what I see here.
> 
> The timeout value in tst-fclose.c is in seconds.  I verified that if
> the doubly-linked list wasn't used, tst-fclose failed with timeout.

Ah, OK, you mean 2s is the threshold used in the automated test, makes sense.
But to illustrate/explain, it is worth mentioning it actually drops to milliseconds.
____________________________________________________________________________________________________________
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.

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

[H.J. Lu]

On Tue, Apr 30, 2024 at 11:11 AM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Tue, Apr 30, 2024 at 11:00 AM <alexandre.ferrieux@orange.com> wrote:
> >
> >
> >
> > On 30/04/2024 19:20, H.J. Lu wrote:
> > >
> > > From: Alexandre Ferrieux <alexandre.ferrieux@orange.com>
> > >
> > > 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.
> > >
> > >
> > > Co-Authored-By: H.J. Lu <hjl.tools@gmail.com>
> >
> > Thanks a lot, H.J., for finishing the job !
> > And thanks also for providing the explanation about the semantics of the
> > vtable_offset nullity check, that was not obvious for an outside observer like me :)
>
> I submitted a test:
>
> https://patchwork.sourceware.org/project/glibc/list/?series=33313
>
> to verify that the old binary linked against glibc 2.0 works.
>
> > (If I missed a README explaining all this, thanks for giving me the link)
> >
> >  > As tst-fclose.c shows, after opening 2 million (FILE*), the fclose() of
> >  > 100 of them takes more than a few seconds without the patch, and under
> >  > 2 seconds with it.
> >
> > Don't you mean "under 2 milliseconds" ? That's closer to what I see here.
>
> The timeout value in tst-fclose.c is in seconds.  I verified that if
> the doubly-linked
> list wasn't used, tst-fclose failed with timeout.
>
>

I sent out the v2 patch:

https://patchwork.sourceware.org/project/glibc/list/?series=33319

to remove fcloseall which has been deprecated.

-- 
H.J.

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

[H.J. Lu]

On Tue, Apr 30, 2024 at 11:00 AM <alexandre.ferrieux@orange.com> wrote:
>
>
>
> On 30/04/2024 19:20, H.J. Lu wrote:
> >
> > From: Alexandre Ferrieux <alexandre.ferrieux@orange.com>
> >
> > 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.
> >
> >
> > Co-Authored-By: H.J. Lu <hjl.tools@gmail.com>
>
> Thanks a lot, H.J., for finishing the job !
> And thanks also for providing the explanation about the semantics of the
> vtable_offset nullity check, that was not obvious for an outside observer like me :)

I submitted a test:

https://patchwork.sourceware.org/project/glibc/list/?series=33313

to verify that the old binary linked against glibc 2.0 works.

> (If I missed a README explaining all this, thanks for giving me the link)
>
>  > As tst-fclose.c shows, after opening 2 million (FILE*), the fclose() of
>  > 100 of them takes more than a few seconds without the patch, and under
>  > 2 seconds with it.
>
> Don't you mean "under 2 milliseconds" ? That's closer to what I see here.

The timeout value in tst-fclose.c is in seconds.  I verified that if
the doubly-linked
list wasn't used, tst-fclose failed with timeout.

-- 
H.J.

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

[alexandre.ferrieux]

On 30/04/2024 19:20, H.J. Lu wrote:
> 
> From: Alexandre Ferrieux <alexandre.ferrieux@orange.com>
> 
> 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.
> 
> 
> Co-Authored-By: H.J. Lu <hjl.tools@gmail.com>

Thanks a lot, H.J., for finishing the job !
And thanks also for providing the explanation about the semantics of the 
vtable_offset nullity check, that was not obvious for an outside observer like me :)

(If I missed a README explaining all this, thanks for giving me the link)

 > As tst-fclose.c shows, after opening 2 million (FILE*), the fclose() of
 > 100 of them takes more than a few seconds without the patch, and under
 > 2 seconds with it.

Don't you mean "under 2 milliseconds" ? That's closer to what I see here.
____________________________________________________________________________________________________________
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.

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

[H.J. Lu]

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

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.

As tst-fclose.c shows, after opening 2 million (FILE*), the fclose() of
100 of them takes more than a few seconds without the patch, and under
2 seconds with it.

Co-Authored-By: H.J. Lu <hjl.tools@gmail.com>
---
 libio/Makefile                 |  1 +
 libio/bits/types/struct_FILE.h |  4 +--
 libio/genops.c                 | 26 +++++++++++++++
 libio/stdfiles.c               | 15 +++++++++
 libio/tst-fclose.c             | 60 ++++++++++++++++++++++++++++++++++
 5 files changed, 104 insertions(+), 2 deletions(-)
 create mode 100644 libio/tst-fclose.c

diff --git a/libio/Makefile b/libio/Makefile
index 0c1f16ee3b..7f598c840c 100644
--- a/libio/Makefile
+++ b/libio/Makefile
@@ -94,6 +94,7 @@ tests = \
   tst-eof \
   tst-ext \
   tst-ext2 \
+  tst-fclose \
   tst-fgetc-after-eof \
   tst-fgetwc \
   tst-fgetws \
diff --git a/libio/bits/types/struct_FILE.h b/libio/bits/types/struct_FILE.h
index 7cdaae86f8..d8d26639d1 100644
--- a/libio/bits/types/struct_FILE.h
+++ b/libio/bits/types/struct_FILE.h
@@ -92,10 +92,10 @@ struct _IO_FILE_complete
   struct _IO_wide_data *_wide_data;
   struct _IO_FILE *_freeres_list;
   void *_freeres_buf;
-  size_t __pad5;
+  struct _IO_FILE **_prevchain;
   int _mode;
   /* Make sure we don't get into trouble again.  */
-  char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
+  char _unused2[15 * sizeof (int) - 5 * sizeof (void *)];
 };
 
 /* These macros are used by bits/stdio.h and internal headers.  */
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);
diff --git a/libio/stdfiles.c b/libio/stdfiles.c
index cd8eca8bf3..d607fa02e0 100644
--- a/libio/stdfiles.c
+++ b/libio/stdfiles.c
@@ -54,4 +54,19 @@ 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_;
+
+/* Finish the double-linking for stdfiles as static initialization
+   cannot.  */
+
+__THROW __attribute__ ((constructor))
+static void
+_IO_stdfiles_init (void)
+{
+  struct _IO_FILE **f;
+  for (f = (struct _IO_FILE **) &_IO_list_all;
+       *f != NULL;
+       f = &(*f)->_chain)
+    (*f)->_prevchain = f;
+}
+
 libc_hidden_data_def (_IO_list_all)
diff --git a/libio/tst-fclose.c b/libio/tst-fclose.c
new file mode 100644
index 0000000000..792c69beec
--- /dev/null
+++ b/libio/tst-fclose.c
@@ -0,0 +1,60 @@
+/* Verify fclose performance with many opened files.
+   Copyright (C) 2024 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <support/test-driver.h>
+
+#define N 2000000
+#define M 100
+
+static int
+do_test (void)
+{
+  FILE *ff, *keep[M];
+  int i;
+
+  fprintf (stderr, "Preparing %d FILEs ...\n", N);
+  fflush (stderr);
+  for (i = 0; i < N; i++)
+    {
+      ff = fdopen (STDIN_FILENO, "r");
+      if (!ff)
+	{
+	  fprintf (stderr, "### failed to fdopen: %m\n");
+	  return EXIT_FAILURE;
+	}
+      if (i < M)
+	keep[i] = ff;
+    }
+  fprintf (stderr, "Now fclosing ...");
+  fflush (stderr);
+  for (i = 0; i < M; i++)
+    fclose (keep[i]);
+  fprintf (stderr, "DONE\n");
+  fflush (stderr);
+  fprintf (stderr, "Now calling fcloseall( )...");
+  fcloseall ();
+  fprintf (stderr, "DONE\n");
+  fflush (stderr);
+  return EXIT_SUCCESS;
+}
+
+#define TIMEOUT 2
+#include <support/test-driver.c>
-- 
2.44.0