From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id BD86D3857BAD for ; Thu, 2 Jun 2022 15:09:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BD86D3857BAD Received: from pps.filterd (m0098404.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 252ELDCt018195; Thu, 2 Jun 2022 15:09:51 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3gewxga9ab-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 02 Jun 2022 15:09:51 +0000 Received: from m0098404.ppops.net (m0098404.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 252EpbFS001777; Thu, 2 Jun 2022 15:09:51 GMT Received: from ppma06fra.de.ibm.com (48.49.7a9f.ip4.static.sl-reverse.com [159.122.73.72]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3gewxga99p-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 02 Jun 2022 15:09:50 +0000 Received: from pps.filterd (ppma06fra.de.ibm.com [127.0.0.1]) by ppma06fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 252F6ETb014423; Thu, 2 Jun 2022 15:09:48 GMT Received: from b06avi18626390.portsmouth.uk.ibm.com (b06avi18626390.portsmouth.uk.ibm.com [9.149.26.192]) by ppma06fra.de.ibm.com with ESMTP id 3gbcb7ng74-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 02 Jun 2022 15:09:48 +0000 Received: from d06av24.portsmouth.uk.ibm.com (mk.ibm.com [9.149.105.60]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 252F9fs914811410 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 2 Jun 2022 15:09:41 GMT Received: from d06av24.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id EAC5242042; Thu, 2 Jun 2022 15:09:45 +0000 (GMT) Received: from d06av24.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 9DF374203F; Thu, 2 Jun 2022 15:09:45 +0000 (GMT) Received: from [9.171.42.87] (unknown [9.171.42.87]) by d06av24.portsmouth.uk.ibm.com (Postfix) with ESMTP; Thu, 2 Jun 2022 15:09:45 +0000 (GMT) Message-ID: <4ca5a328b7e2d1a9b9287b8c3a3b2fe525b42c3c.camel@linux.ibm.com> Subject: Re: [PATCH 2/5] gdbsupport: Introduce interval_tree From: Ilya Leoshkevich To: Pedro Alves , Tom Tromey , Andrew Burgess Cc: Andreas Arnez , gdb-patches@sourceware.org Date: Thu, 02 Jun 2022 17:09:45 +0200 In-Reply-To: <52e0e168-3ad4-df0e-5b46-2856e82b5d47@palves.net> References: <20220602133546.2948282-1-iii@linux.ibm.com> <20220602133546.2948282-3-iii@linux.ibm.com> <94eef992-ff81-b994-b30f-daf26b6c5915@palves.net> <52e0e168-3ad4-df0e-5b46-2856e82b5d47@palves.net> Content-Type: text/plain; charset="UTF-8" User-Agent: Evolution 3.42.4 (3.42.4-2.fc35) MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 8tQjs99AOtRmpxPS94jlwzPfY3r2eAxk X-Proofpoint-ORIG-GUID: FTpgAoOOOoBwkL57n73LEwNO97rmS1aC X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.874,Hydra:6.0.517,FMLib:17.11.64.514 definitions=2022-06-02_03,2022-06-02_01,2022-02-23_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 phishscore=0 impostorscore=0 suspectscore=0 mlxlogscore=999 lowpriorityscore=0 adultscore=0 mlxscore=0 spamscore=0 bulkscore=0 malwarescore=0 priorityscore=1501 clxscore=1015 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206020063 X-Spam-Status: No, score=-3.9 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 02 Jun 2022 15:09:57 -0000 On Thu, 2022-06-02 at 15:37 +0100, Pedro Alves wrote: > On 2022-06-02 15:12, Pedro Alves wrote: > > On 2022-06-02 14:35, Ilya Leoshkevich wrote: > > > > > > Adding N JITed sections has the complexity O((N**2)*log(N)), > > > because > > > adding each section involves breakpoint handling, which needs to > > > resolve PCs and thus calls update_section_map().  When N is > > > around 10k, > > > this renders GDB unusable. > > > > Does this adding of N JITed sections happen in batch?  Like, is > > this from > > jit_inferior_init, where we loop over JIT objects?  Or is it so > > that we > > get notified about JIT objects, one at a time? > > > > In places where we add symbols in batch, we defer breakpoint > > re_setting exactly > > to avoid problems like this, via SYMFILE_DEFER_BP_RESET or > > something similar. > > Looks like jit.c doesn't try to do that.  Or is it not possible in > > the scenario > > in question?  Like, doesn't the JIT API let you register more than > > one object > > file at once? > > It has taken me this long to remember that I once wrote a patch > series to > tackle this problem...  :-)  It's been on a branch on sourceware > since 2016... > > See the palves/jit-speedup branch. > > I completely forgot that. > > There, I added a number of patches deferring breakpoint_re_set in > several > different situations, and other simple optimizations that avoid O(N). > It may be those patches are obsolete by now, but maybe they aren't. > > For the section sorting issue itself, the branch has this: > > ~~~~~~~~~~~~~~~~~~ > commit 5cd42e9fb13d25febe3da26595d044a57150cee5 > Author:     Pedro Alves > AuthorDate: Fri Apr 1 01:14:30 2016 +0100 > Commit:     Pedro Alves > CommitDate: Mon Sep 19 15:44:41 2016 +0100 > >     Get rid of sections sorting with qsort and use an incrementally > updated addrmap instead >     >     This gives a massive speed up.  The problem with the qsort is > that we >     qsort for any one of the thousands of jit loads/unloads, and when > you >     have thousands of objfiles, that gets very slow.  In this > scenario, >     we're constantly adding/removing a handfull of obj_sections to a > set >     of thousands of already-sorted obj_sections.  It's much cheaper > to do >     an incremental update. >     >     I'm using a mutable addrmap for this, but I needed to add a new >     primitive that allowed updating a region's object, to handle the > case >     of overlapping sections.  The only primitive available, only > allows >     setting a value to a currently-NULL region. > > ~~~~~~~~~~~~~~~~~~ > > it talks about qsort because back when we hadn't yet moved to C++ > std::sort. > > As you see, I was using an addrmap for this (gdb/addrmap.h), which is > a data structure > we already have.  I wonder whether the new data structure is really > needed.  That's > a question I was going to raise anyhow, until I remembered I had once > already attempted it > (and seen that it works). Ah, interesting - I wasn't aware of addrmap. You even handle overlapping sections conservatively by associating more than one with each address range: struct obj_section_map_addrmap_value { VEC (obj_section_p) *sections; }; This may use excessive memory if we have sections like [0,0], [0,1], [0,2], ..., but hopefully that's not something that happens in the real life often. It's also interesting that you drop section_map_dirty and just apply the changes right away. I wasn't sure whether delaying the processing was needed for something other than performance, so I kept it. Same for inhibit_updates. I will try to play with addrmap and see if it works for me.