Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.arch
Subject: Re: MSI interrupts
Date: Mon, 24 Mar 2025 19:08:58 -0700
Organization: A noiseless patient Spider
Lines: 58
Message-ID: <vrt37r$27c13$4@dont-email.me>
References: <vqto79$335c6$1@dont-email.me>
 <33d525dc9450a654173f9313f0564224@www.novabbs.org>
 <jwva59a48v6.fsf-monnier+comp.arch@gnu.org>
 <96987d473656f296ec63c30626a46730@www.novabbs.org>
 <vrsf9o$c6m$1@reader1.panix.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 25 Mar 2025 03:08:59 +0100 (CET)
Injection-Info: dont-email.me; posting-host="5e2174216670af0d17933d91728d06f2";
	logging-data="2338851"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18/Yb14xaPe9xLaRTjhO67qzAdh/G0hZnE="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:5uK/6E6PqwtR77LFftxdam1aS1k=
Content-Language: en-US
In-Reply-To: <vrsf9o$c6m$1@reader1.panix.com>
Bytes: 3922

On 3/24/2025 1:28 PM, Dan Cross wrote:
> In article <96987d473656f296ec63c30626a46730@www.novabbs.org>,
> MitchAlsup1 <mitchalsup@aol.com> wrote:
>> On Mon, 24 Mar 2025 18:02:25 +0000, Stefan Monnier wrote:
>>
>>> MitchAlsup1 [2025-03-24 17:36:28] wrote:
>>>> On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:
>>>>> Consider something as simple as popping an item off of the front
>>>>> of a queue and inserting it into an ordered singly-linked list:
>>> [...]
>>>> I have almost that in the documentation for my ATOMIC stuff::
>>>> The following code moves a doubly linked element from one place
>>>> in a concurrent data structure to another without any interested
>>>> 3rd party being able to see that the element is now within the
>>>> CDS at any time::
>>>
>>> Would your "ATOMIC stuff" really handle Dan's example, tho?
>>> A key element in Dan's example if the "ordered singly-linked list",
>>> i.e. you need to walk the list an unbounded number of steps until you
>>> can find the insertion point, so I don't think you can do the whole
>>> thing inside your ATOMIC stuff.
>>
>> Technically, yes, you can put a search loop in an ATOOMIC event.
>> Whether you want to or not is a different story. My example
>> illustrated the ATOMIC manipulation of the event without a search.
>>
>> In addition, if the search it long, code developer should either
>> to the search before the event, or grab a Mutex to prevent
>> interference during the search and rest of the critical region.
> 
> The problem, as specified, excluded this idea that the list was
> long.
> 
> The point was simply to show a scenario where your atomic
> operation proposal breaks down, and where you might want to
> disable interrupt delivery.  The point wasn't to ask whether
> the specific problem could be recast in a different way; it
> probably can.  The question was to ask whether your proposal
> could support that specific problem.  I don't see how it can.
> 
>>> IOW, you'd have to somehow move the list-walk outside of the atomic
>>> section.
>>
>> Yes,
>>
>>> E.g. if you know elements are only ever removed from the tail of the
>>> list, you can presumably walk the list outside of the ATOMIC stuff and
>>> then do the "remove from the queue and insert into the list" atomically
>>> since it's a small&finite number of steps (with a test to loop back to
>>> the list-walk if someone else inserted or removed anything at that point
>>> in the mean time).
>>
>> Or maintain a tail pointer.
> 
> There's no guarantee that the tail is the correct place to
> insert the element, vis the order of the elements.

https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html