From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1M6Tcs-0006FN-BP for qemu-devel@nongnu.org; Tue, 19 May 2009 14:01:18 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1M6Tcn-0006Eb-OS for qemu-devel@nongnu.org; Tue, 19 May 2009 14:01:17 -0400 Received: from [199.232.76.173] (port=49607 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1M6Tcn-0006EY-JY for qemu-devel@nongnu.org; Tue, 19 May 2009 14:01:13 -0400 Received: from mx20.gnu.org ([199.232.41.8]:29865) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1M6Tcn-00006B-3t for qemu-devel@nongnu.org; Tue, 19 May 2009 14:01:13 -0400 Received: from mail.codesourcery.com ([65.74.133.4]) by mx20.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1M6Tcl-0005k5-RJ for qemu-devel@nongnu.org; Tue, 19 May 2009 14:01:12 -0400 Date: Tue, 19 May 2009 11:01:10 -0700 From: Nathan Froyd Subject: Re: [Qemu-devel] Re: [PATCH] fix gdbstub support for multiple threads in usermode Message-ID: <20090519180110.GE23911@codesourcery.com> References: <1242156943-27850-1-git-send-email-froydnj@codesourcery.com> <4A09E1C2.9020302@web.de> <20090519150636.GA23911@codesourcery.com> <4A12E418.4040403@web.de> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4A12E418.4040403@web.de> List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org On Tue, May 19, 2009 at 06:53:44PM +0200, Jan Kiszka wrote: > Nathan Froyd wrote: > > The best way I can think of to do this is to maintain a > > separately-chained list of CPUStates (through a new field similar to > > next_cpu) ordered by gdbstub_index. Grabbing a new gdbstub_index then > > walks through the list, looking for "holes" between adjacent entries in > > the list. A new gdbstub_index is then picked if we find a hole; we die > > if we can't find a hole. > > Why creating a new list? Just generate a new index and then walk through > all so far registered CPUStates until no collision is found. Do you mean something like: new_index = 0 restart: for cpu in all_cpus: if new_index == cpu.gdbstub_index new_index += 1 goto restart; new_cpu.gdbstub_index = new_index I was trying to keep it a linear-time algorithm, and the above is potentially quadratic. (Not merely an academic exercise, either; spinning up your first N threads will be enough to trigger quadratic behavior.) I don't think you can say: new_index = 0 for cpu in all_cpus: if new_index == cpu.gdbstub_index new_index = cpu.gdbstub_index + 1 new_cpu.gdbstub_index = new_index (i.e. maximum+1 of all existing cpus) either, since that fails for a list that looks like: 1 -> 0 You could iterate, of course, but then you're just back to quadratic behavior. Nothing promises that the cpu list will be kept in sorted order according to some criteria. (A quick examination of things indicates the list might be accidentally sorted by time of creation--and thereby by gdbstub_index--but that falls apart once you wrap gdbstub_index, of course.) AFAICS, you need the cpus sorted by their gdbstub_index to keep linear time bounds. If using a quadratic algorithm is OK, then I'll just do that, but that doesn't seem like a good idea, especially since you're imposing a large slowdown on everything for debugging support which might never get used. Apologies if I'm missing something obvious here. -Nathan