[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] Re: [PATCH] fix gdbstub support for multiple threads in use
From: |
Jan Kiszka |
Subject: |
[Qemu-devel] Re: [PATCH] fix gdbstub support for multiple threads in usermode |
Date: |
Wed, 20 May 2009 08:39:12 +0200 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686 (x86_64); de; rv:1.8.1.12) Gecko/20080226 SUSE/2.0.0.12-1.1 Thunderbird/2.0.0.12 Mnenhy/0.7.5.666 |
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 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.
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
signature.asc
Description: OpenPGP digital signature