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

["H.J. Lu" <hjl.tools@gmail.com>]

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.