Path: ...!weretis.net!feeder9.news.weretis.net!panix!.POSTED.spitfire.i.gajendra.net!not-for-mail
From: cross@spitfire.i.gajendra.net (Dan Cross)
Newsgroups: comp.arch
Subject: Re: MSI interrupts
Date: Mon, 24 Mar 2025 23:27:34 -0000 (UTC)
Organization: PANIX Public Access Internet and UNIX, NYC
Message-ID: <vrspp6$jpn$1@reader1.panix.com>
References: <vqto79$335c6$1@dont-email.me> <96987d473656f296ec63c30626a46730@www.novabbs.org> <vrsf9o$c6m$1@reader1.panix.com> <684d32898ec85b91bcb9dcdb97d8065a@www.novabbs.org>
Injection-Date: Mon, 24 Mar 2025 23:27:34 -0000 (UTC)
Injection-Info: reader1.panix.com; posting-host="spitfire.i.gajendra.net:166.84.136.80";
	logging-data="20279"; mail-complaints-to="abuse@panix.com"
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
Originator: cross@spitfire.i.gajendra.net (Dan Cross)
Bytes: 5094
Lines: 94

In article <684d32898ec85b91bcb9dcdb97d8065a@www.novabbs.org>,
MitchAlsup1 <mitchalsup@aol.com> wrote:
>On Mon, 24 Mar 2025 20:28:40 +0000, 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.
>
>My ATOMIC stuff allows for the construction, in SW, of pretty
>much any ATOMIC primitive anyone would like. It is, in general,
>not suited to guard critical regions, but to grab the lock which
>does.

Ok, that's good to understand.

>Most uses of My ATOMIC stuff is to grab/change/update data
>that then guards various critical regions. More like a multi-
>valued version of LDL-STC.

I don't see how constructing the primitive that way is terribly
useful compared to just issuing multiple load-locked/store-cond
instructions; in particular, it doesn't seem like the sort of
thing that composes well: every sequence that uses it must be
coded to use it, explicitly, instead of just nesting calls to
"lock".

>>                              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.
>
>To the question posed, you should just grab the lock/mutex.

That's fine, then.  But this is another example of a place where 
one probably wants to disable interrupts while in the critical
section, to avoid being preempted while holding the lock.

>>>> 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.
>
>If the element pointer updates and the tail pointer update are inside
>one of my ATOMIC events, then you are sure that the tail pointer is
>always pointing at the last element in the list (if there is one).

But that's irrelevant.  The goal is to insert into a sorted list
and, again, the last element is not necessarily the correct
place to insert (or append).

	- Dan C.