From patchwork Fri Apr 26 14:18:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: alexandre.ferrieux@orange.com X-Patchwork-Id: 1928217 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=orange.com header.i=@orange.com header.a=rsa-sha256 header.s=orange002 header.b=fA4MtjXP; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4VQvx96vb6z1yP2 for ; Sat, 27 Apr 2024 00:19:25 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AD7F0384AB77 for ; Fri, 26 Apr 2024 14:19:22 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from smtp-out.orange.com (smtp-out.orange.com [80.12.126.236]) by sourceware.org (Postfix) with ESMTPS id 645D3384AB56 for ; Fri, 26 Apr 2024 14:19:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 645D3384AB56 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=orange.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=orange.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 645D3384AB56 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=80.12.126.236 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1714141145; cv=none; b=CrbaC/yxlxrJYjmXe3m/sCuu3ACeTAPNc8kHeRyXF2hPAcBli2BVP1CBj7QfnvZ5qgqgwaS33Ib86pHH8PyIL/mR/Pht0YPV+ItwghIW6SzZ2bGhaV9KACOajfgCv6YAofBwe6nlNI30mhogSO5iqsV4hpZDc2L8jJVpQ/uzbcQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1714141145; c=relaxed/simple; bh=fbvhyOEqZ+kFI+RUzgs4eoJPta6kfSg+XqohqIyFoOc=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=pjvxD5U6DiGsPNzVQ7BAo77Xv5g+Ow+91kP1yzAU9L+/CdA8bFgWlPHZwHXzqQPdR4ynyFdckczsajHlmLFz6b5I6bkRBcd/Cxl6E4k6VV8QGWdeAXs6dPwni9Rfop+0UUKsYgX+Y7GqUGRHi1me+Ho/yjpLeHSOPGfF6RgMp+0= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=orange.com; i=@orange.com; q=dns/txt; s=orange002; t=1714141143; x=1745677143; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=/mocdEFpjO6t0BlJOkZSCkdFCPpwfMhj0OiG/uRBuZw=; b=fA4MtjXPfBHMyeU2AZVaIghoo4Lv3v8AhD2ts6yU33knfUBxpEdkPSND 2KGn6mxIWLCvZf6E3nLzrQzQxMHsucU2SpJb2nUGe03tnLkAGWDkzVSJG gUpVWBPaPgTiT6v7LWFv3eSciRqKzmSoGDFt64q2eYtKeD8k6xrzXCUhx bbgWEPh19RJ9ch3SNCH3tEtzhGy/I4IpFA1MAZHgJ+f+I2CPvKF+f+v8o HrSKcoaCWYH6uqjYPMfodffcLQdh5F+3njKj9kwv1/ek8+PMdx/dBDf7x v+7iaoLSFrnt9qE954rCq/LGLecrAVr5cmvKm/TsXYdROfypNwWcH+rX9 Q==; Received: from unknown (HELO opfedv3rlp0c.nor.fr.ftgroup) ([x.x.x.x]) by smtp-out.orange.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 26 Apr 2024 16:19:01 +0200 Received: from l-mail-int.rd.francetelecom.fr (HELO l-mail-int) ([x.x.x.x]) by opfedv3rlp0c.nor.fr.ftgroup with ESMTP; 26 Apr 2024 16:19:00 +0200 Received: from lat6466.rd.francetelecom.fr ([x.x.x.x]) by l-mail-int with esmtp (Exim 4.94.2) (envelope-from ) id 1s0MPa-00EezJ-Lm; Fri, 26 Apr 2024 16:19:00 +0200 X-IronPort-AV: E=Sophos;i="6.07,232,1708383600"; d="scan'208";a="138143830" From: alexandre.ferrieux@orange.com To: libc-alpha@sourceware.org Cc: carlos@redhat.com, Alexandre Ferrieux Subject: [PATCH] Fix #27777 - now use a doubly-linked list for _IO_list_all Date: Fri, 26 Apr 2024 16:18:47 +0200 Message-Id: <20240426141847.2458829-1-alexandre.ferrieux@orange.com> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 X-Spam-Status: No, score=-3.1 required=5.0 tests=BAYES_50, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FOREIGN_BODY1, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SCC_5_SHORT_WORD_LINES, SPF_HELO_PASS, SPF_NONE, TXREP, UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org From: Alexandre Ferrieux 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 --- 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 #include #include +#include #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)