From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1M6hPe-0007dc-Aw for qemu-devel@nongnu.org; Wed, 20 May 2009 04:44:34 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1M6hPZ-0007c7-HP for qemu-devel@nongnu.org; Wed, 20 May 2009 04:44:33 -0400 Received: from [199.232.76.173] (port=56543 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1M6hPZ-0007c4-5P for qemu-devel@nongnu.org; Wed, 20 May 2009 04:44:29 -0400 Received: from fmmailgate02.web.de ([217.72.192.227]:57481) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1M6hPY-00011T-If for qemu-devel@nongnu.org; Wed, 20 May 2009 04:44:28 -0400 Received: from smtp08.web.de (fmsmtp08.dlan.cinetic.de [172.20.5.216]) by fmmailgate02.web.de (Postfix) with ESMTP id 72F77FFED107 for ; Wed, 20 May 2009 08:39:18 +0200 (CEST) Received: from [88.66.121.94] (helo=[192.168.1.3]) by smtp08.web.de with asmtp (TLSv1:AES256-SHA:256) (WEB.DE 4.110 #277) id 1M6fSQ-00083n-00 for qemu-devel@nongnu.org; Wed, 20 May 2009 08:39:18 +0200 Message-ID: <4A13A590.8040301@web.de> Date: Wed, 20 May 2009 08:39:12 +0200 From: Jan Kiszka MIME-Version: 1.0 References: <1242156943-27850-1-git-send-email-froydnj@codesourcery.com> <4A09E1C2.9020302@web.de> <20090519150636.GA23911@codesourcery.com> <4A12E418.4040403@web.de> <20090519180110.GE23911@codesourcery.com> In-Reply-To: <20090519180110.GE23911@codesourcery.com> Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigEB46C182013DE0601859DE0F" Sender: jan.kiszka@web.de Subject: [Qemu-devel] Re: [PATCH] fix gdbstub support for multiple threads in usermode List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigEB46C182013DE0601859DE0F Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Nathan Froyd wrote: > 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 the= n >>> 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 d= ie >>> if we can't find a hole. >> Why creating a new list? Just generate a new index and then walk throu= gh >> all so far registered CPUStates until no collision is found. >=20 > Do you mean something like: >=20 > new_index =3D 0 > restart: > for cpu in all_cpus: > if new_index =3D=3D cpu.gdbstub_index > new_index +=3D 1 > goto restart; > new_cpu.gdbstub_index =3D new_index >=20 > 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: >=20 > new_index =3D 0 > for cpu in all_cpus: > if new_index =3D=3D cpu.gdbstub_index > new_index =3D cpu.gdbstub_index + 1 > new_cpu.gdbstub_index =3D new_index >=20 > (i.e. maximum+1 of all existing cpus) either, since that fails for a > list that looks like: >=20 > 1 -> 0 >=20 > You could iterate, of course, but then you're just back to quadratic > behavior. >=20 > 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. I see. So we basically have two options: 1. Stick head in sand - we will never see so many threads in reality, so neither wrap-around nor performance matters. 2. Go for a bitmap-based search of the next free ID (reducing the ID space so that the bitmap has a reasonable size) But I have no clue if and how long option 1 will suffice as I have no idea how many long-running highly dynamic multi-threaded use cases there are or will be for qemu user mode. But if you find option 2 easy enough to implement, I would do this nevertheless. Jan --------------enigEB46C182013DE0601859DE0F Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.9 (GNU/Linux) Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org iEYEARECAAYFAkoTpZUACgkQniDOoMHTA+la1ACeNgeMZMBlmcAXmYKYgQ9wfnRe VQYAnjWMQ5SHfyYptsW63cISb9Yzsr0c =5RHX -----END PGP SIGNATURE----- --------------enigEB46C182013DE0601859DE0F--