From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on starla X-Spam-Level: X-Spam-Status: No, score=-0.9 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 9DD7F1F44D for ; Fri, 26 Apr 2024 14:19:29 +0000 (UTC) Authentication-Results: dcvr.yhbt.net; 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 Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DDAE23858402 for ; Fri, 26 Apr 2024 14:19:28 +0000 (GMT) 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 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit 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+e=80x24.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) -- 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.