diff options
author | Alexandre Ferrieux <alexandre.ferrieux@orange.com> | 2024-05-16 05:54:30 -0700 |
---|---|---|
committer | H.J. Lu <hjl.tools@gmail.com> | 2024-05-17 14:13:25 -0700 |
commit | 2a99e2398d9d717c034e915f7846a49e623f5450 (patch) | |
tree | bbd97d056e8aaa0fbd8aece4f7a6c055c638fd3c /libio/genops.c | |
parent | a81cdde1cb9d514fc8f014ddf21771c96ff2c182 (diff) | |
download | glibc-2a99e2398d9d717c034e915f7846a49e623f5450.zip glibc-2a99e2398d9d717c034e915f7846a49e623f5450.tar.gz glibc-2a99e2398d9d717c034e915f7846a49e623f5450.tar.bz2 |
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>
Diffstat (limited to 'libio/genops.c')
-rw-r--r-- | libio/genops.c | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/libio/genops.c b/libio/genops.c index bc45e60..994ee9c 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); |