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