On 11/7/2023 11:27 AM, Johnny Billquist wrote:
> On 2023-11-07 01:18, Arne Vajhøj wrote:
>> On 11/6/2023 6:31 AM, Johnny Billquist wrote:
>>> Read ahead is something that the system can easily do both for normal
>>> I/O and memory mapped I/O. It's just a question of speculative reads
>>> assuming some pattern by the program. Most commonly that you are
>>> reading files sequentially from start to finish.
>>
>> $QIO(w) and $IO_PERFORM(W) could.
>>
>> But at least for $QIO(W) then I would be very surprised if it did. It is
>> from before VIOC/XFC so originally it did not have anywhere to
>> store read ahead data. VMS engineering could have changed
>> behavior when VIOC/XFC was introduced. But I doubt it.
>>
>> $IO_PERFORM(W) maybe. But I think the spirit is still
>> "do exactly what the developer asked for and nothing more".
>
> I'd say memory mapped I/O falls in the exact same category here.

Not exact.

$QIO(W) and $IO_PERFORM(W) read means read these X bytes
now and write means write these X bytes now.

$CRMPSC and memory access read means read at least
these X bytes now and write means write these X bytes
either when convenient or when explicit flushed/deleted.

Arne

In article <uidpd1$6s2$4@news.misty.com>,
Johnny Billquist <bqt@softjar.se> wrote:
>On 2023-11-04 15:14, Dan Cross wrote:
>>>>[snip]
>>>> Consider the problem of a per-core queue with work-stealing;
>>>> the specifics of what's in the queue don't matter so much as the
>>>> overall structure of the problem: items in the queue might
>>>> represent IO requests, or they may represent runnable threads,
>>>> or whatever. Anyway, a core will usually process things on
>>>> its own local queue, but if it runs out of things to do, it
>>>> may choose some victim and steal some work from it.
>>>> Conventionally, this will involve everyone taking locks on
>>>> these queues, but that's ok: we expect that work stealing is
>>>> pretty rare, and that usually a core is simply locking its own
>>>> queue, which will be an uncontended write on a cacheline it
>>>> already owns. In any event, _most of the time_ the overhead
>>>> of using a "lock" will be minimal (assuming relatively simply
>>>> spinlocks or MCS locks or something like that).
>>>
>>> I generally agree with everything you posted. But I think it's
>>> unfortunate that you bring in cache lines into this, as it's somewhat
>>> incorrect to talk about "owning" a cache line, and cache lines are not
>>> really that relevant at all in this context.
>>
>> This is an odd thing to say. It's quite common to talk about
>> core ownership of cache lines in both MESI and MOESI, which are
>> the cache coherency protocols in use on modern x86 systems from
>> both Intel and AMD, respectively. Indeed, the "O" in "MOESI" is
>> for "owned" (https://en.wikipedia.org/wiki/MOESI_protocol).
>
>I think we're talking past each other.

Yes. See below.

>> Cache lines and their ownership are massively relevant in the
>> context of mutual exclusion, atomic operations, and working on
>> shared memory generally.
>
>You are then talking about it in the sense that if a CPU writes to
>memory, and it's in the cache, then yes, you get ownership properties
>then/there. Primarily because you are not immediately writing back to
>main memory, and other CPUs are allowed to then hold read-only copies. I
>sortof covered that exact topic further down here, about either
>invalidate or update the caches of other CPUs. And it also holds that
>other CPUs cannot freely write or update those memory cells when another
>CPU holds a dirty cache about it.

Well, no; in the protocols in use on x86, if you have exclusive
access to a cache line, in either the exclusive or modified
state, then any other cache's copy of that line is invalidated.

MOESI augments this by allowing sharing of dirty data via the
OWNED state, allowing for cache-to-cache updates.

>But before the CPU writes the data, it never owns the cache line. So it
>don't make sense to say "uncontended write on a cacheline it already
>owns". Ownership only happens when you do the write. And once you've
>written, you own it.

This ignores the context; see what I wrote above.

To recap, I was hypothesizing a multiprocessor system with
per-CPU work queues with work stealing. In such a system, an
implementation may be to use a spinlock for each CPU's queue: in
the rare cases where one wants to steal work, one must lock some
other CPU's queue, _BUT_, in the usual scenario when the per-CPU
queue is uncontended, the local worker will lock the queue,
remove an item from it, unlock the queue, do some work, _and
then repeat_. Note that once it acquires the lock on its queue
the CPU will own the corresponding cacheline; since we assume
work stealing is rare, it is likely _it will still own it on
subsequent iterations of this loop._ Hence, making an
uncontended write on a cache line it already owns; here, it owns
it from the last time it made that same write.

>I'm probably trying to make it too simple when I write about it. Trying
>to avoid going overly-technical has its risks...

Yes.

>>> But that's all there is to it. Now, it is indeed very costly if you have
>>> many CPUs trying to spin-lock on the same data, because each one will be
>>> hitting the same memory, causing a big pressure on that memory address.
>>
>> More accurately, you'll be pushing the associated cache line
>> through a huge number of state transitions as different cores
>> vye for exclusive ownership of the line in order to write the
>> lock value. Beyond a handful of cores, the generated cache
>> coherency traffic begins to dominate, and overall throughput
>> _decreases_.
>>
>> This is of paramount importance when we start talking about
>> things like synchronization primitives, which are based on
>> atomic updates to shared memory; cache-inefficient algorithms
>> simply do not scale beyond a handful of actors, and why things
>> like MCS locks or CHM locks are used on many-core machines.
>> See, for example:
>> https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf
>
>Yes. This is the scaling problem with spinlocks. Cache coherency starts
>becoming costly. Having algorithms or structures that allow locking to
>not be localized to one address is an important piece to help alleviate it.

Not just address, but _cache lines_, which is why this the topic
is so important. Multiple simultaneous writers to multiple
memory locations in the same cache line can lead to contention
due to false sharing.

>>> (And then we had the PDP-11/74, which had to implement cache coherency
>>> between CPUs without any hardware support...)
>>
>> Sounds rough. :-/
>
>It is. CPU was modified to actually always step around the cache for one
>instruction (ASRB - used for spin locks), and then you manually turn on
>and off cache bypass on a per-page basis, or in general of the CPU,
>depending on what is being done, in order to not get into issues of
>cache inconsistency.

This implies that stores were in a total order, then, and
these uncached instructions were serializing with respect to
other CPUs?

- Dan C.

On 11/7/23 6:04 PM, Arne Vajhøj wrote:
> On 11/7/2023 5:44 PM, Craig A. Berry wrote:
>> On 11/6/23 6:18 PM, Arne Vajhøj wrote:
>>> On 11/6/2023 6:31 AM, Johnny Billquist wrote:
>>
>>>> Read ahead is something that the system can easily do both for
>>>> normal I/O and memory mapped I/O. It's just a question of
>>>> speculative reads assuming some pattern by the program. Most
>>>> commonly that you are reading files sequentially from start to finish.
>>>
>>> $QIO(w) and $IO_PERFORM(W) could.
>>>
>>> But at least for $QIO(W) then I would be very surprised if it did. It is
>>> from before VIOC/XFC so originally it did not have anywhere to
>>> store read ahead data. VMS engineering could have changed
>>> behavior when VIOC/XFC was introduced. But I doubt it.
>>
>> Are you saying that you think merely using $QIO bypasses XFC?  If so,
>> how do you think SHOW MEM/CACHE can give you "Total QIOs"?  And note
>> this from the performance management manual page 72:
>> "I/O service can be optimized at the application level by using RMS
>> global buffers to share caches among processes. This method offers the
>> benefit of satisfying an I/O request without issuing a QIO; whereas
>> system memory software cache (that is, XFC) is checked to satisfy QIOs."
>
> I am sure that $QIO(W) hits XFC. Else there would not be
> much point in XFC.
>
> The question is whether $QIO(W) get more data read into XFC
> than asked for by the user. It could but I doubt it.

Consider what I quoted from the fine manual: "system memory software
cache (that is, XFC) is checked to satisfy QIOs." What would it mean to
read from cache to "satisfy" a QIO other than there may be more data
already in the cache than has been explicitly asked for by the user?

If you're talking about snooping to predict what might be read next and
cache it, it looks like that's an attribute of the volume and of XFC
itself and doesn't have anything to do with the I/O API in use:

https://wiki.vmssoftware.com/VCC_READAHEAD

On Tuesday, November 7, 2023 at 6:17:28 PM UTC-8, Craig A. Berry wrote:
> On 11/7/23 6:04 PM, Arne Vajhøj wrote:
> > On 11/7/2023 5:44 PM, Craig A. Berry wrote:
> >> On 11/6/23 6:18 PM, Arne Vajhøj wrote:
> >>> On 11/6/2023 6:31 AM, Johnny Billquist wrote:
> >>
> >>>> Read ahead is something that the system can easily do both for
> >>>> normal I/O and memory mapped I/O. It's just a question of
> >>>> speculative reads assuming some pattern by the program. Most
> >>>> commonly that you are reading files sequentially from start to finish.
> >>>
> >>> $QIO(w) and $IO_PERFORM(W) could.
> >>>
> >>> But at least for $QIO(W) then I would be very surprised if it did. It is
> >>> from before VIOC/XFC so originally it did not have anywhere to
> >>> store read ahead data. VMS engineering could have changed
> >>> behavior when VIOC/XFC was introduced. But I doubt it.
> >>
> >> Are you saying that you think merely using $QIO bypasses XFC? If so,
> >> how do you think SHOW MEM/CACHE can give you "Total QIOs"? And note
> >> this from the performance management manual page 72:
> >> "I/O service can be optimized at the application level by using RMS
> >> global buffers to share caches among processes. This method offers the
> >> benefit of satisfying an I/O request without issuing a QIO; whereas
> >> system memory software cache (that is, XFC) is checked to satisfy QIOs.."
> >
> > I am sure that $QIO(W) hits XFC. Else there would not be
> > much point in XFC.
> >
> > The question is whether $QIO(W) get more data read into XFC
> > than asked for by the user. It could but I doubt it.
> Consider what I quoted from the fine manual: "system memory software
> cache (that is, XFC) is checked to satisfy QIOs." What would it mean to
> read from cache to "satisfy" a QIO other than there may be more data
> already in the cache than has been explicitly asked for by the user?
>
> If you're talking about snooping to predict what might be read next and
> cache it, it looks like that's an attribute of the volume and of XFC
> itself and doesn't have anything to do with the I/O API in use:
>
> https://wiki.vmssoftware.com/VCC_READAHEAD

This thread has been very educational. I wasn't thinking through the implications of a virtual block data cache that's integrated with the filesystem. The VSI wiki page for the V8.4-2L3 release does a better job of explaining the benefits of the features than anything else I've found:

https://wiki.vmssoftware.com/V8.4-2L3

"The Extended File Cache (XFC) is a virtual block data cache provided with OpenVMS for Integrity servers. Similar to the Virtual I/O Cache, the XFC is a clusterwide, file system data cache. Both file system data caches are compatible and coexist in the OpenVMS Cluster. The XFC improves I/O performance with the following features that are not available with the virtual I/O cache:

Read-ahead caching
Automatic resizing of the cache
Larger maximum cache size
No limit on the number of closed files that can be cached
Control over the maximum size of I/O that can be cached
Control over whether cache memory is static or dynamic
XFC caching attributes of volume can be dynamically modified eliminating the need to dismount the volume."

Where it gets confusing is there definitely is a per-file aspect to caching, since you can set a file or a directory's attributes to write-through or no caching, and the caching attribute is inherited from its parent directory or a previous version of an existing file. "SET FILE /CACHING_ATTRIBUTE". It looks like the "SET FILE" help page covers all of the interesting attributes that you can set programmatically.

At this point, I don't think I trust anyone's explanation for when to use or not use the RMS, QIO, and IO_PERFORM APIs without benchmarking them. The same for optimal buffer sizes. The interesting thing about libuv as an abstraction layer is that you could write a really fast copy file routine that copied files to sockets, other files, over pipes, etc., and then programs using that library would automatically take advantage, because Windows and Linux added transmit-file-to-network calls in the early days of Web servers, so there's a libuv function to perform that operation.

One feature of Windows that libuv knows about that isn't implemented for UNIX is you can open files with the "UV_FS_O_SEQUENTIAL" and "UV_FS_O_RANDOM" flags, which map to the Win32 "FILE_FLAG_SEQUENTIAL_SCAN" and "FILE_FLAG_RANDOM_ACCESS" flags. I've read about filesystems optimizing to try to detect different usage patterns and perform intelligent lookahead accordingly, but not about programs telling the OS how they intend to access the file.

When those flags were added, hard drives were so much slower than today's SSDs, and PCs had so much less RAM, and none of it to spare, so it must have been even more important for the OS to know when and when not to read data ahead. Today, the bottleneck that people are fighting is the overhead of virtualizing fake SCSI hard drives and fake network cards. Virtio helps somewhat, but if what IBM's been doing with KVM on POWER9/10 is any indication, the future lies in optimizing direct paths from the host's PCIe cards into the guest OS. IBM's mainframes have been doing that for a while with their proprietary stuff that emulates the disk geometry of IBM 3390 disk drives from 1990. But they have super-fast networking and IPC between VMs.

On 11/7/2023 9:17 PM, Craig A. Berry wrote:
> On 11/7/23 6:04 PM, Arne Vajhøj wrote:
>> On 11/7/2023 5:44 PM, Craig A. Berry wrote:
>>> On 11/6/23 6:18 PM, Arne Vajhøj wrote:
>>>> On 11/6/2023 6:31 AM, Johnny Billquist wrote:
>>>
>>>>> Read ahead is something that the system can easily do both for
>>>>> normal I/O and memory mapped I/O. It's just a question of
>>>>> speculative reads assuming some pattern by the program. Most
>>>>> commonly that you are reading files sequentially from start to finish.
>>>>
>>>> $QIO(w) and $IO_PERFORM(W) could.
>>>>
>>>> But at least for $QIO(W) then I would be very surprised if it did.
>>>> It is
>>>> from before VIOC/XFC so originally it did not have anywhere to
>>>> store read ahead data. VMS engineering could have changed
>>>> behavior when VIOC/XFC was introduced. But I doubt it.
>>>
>>> Are you saying that you think merely using $QIO bypasses XFC?  If so,
>>> how do you think SHOW MEM/CACHE can give you "Total QIOs"?  And note
>>> this from the performance management manual page 72:
>>> "I/O service can be optimized at the application level by using RMS
>>> global buffers to share caches among processes. This method offers
>>> the benefit of satisfying an I/O request without issuing a QIO;
>>> whereas system memory software cache (that is, XFC) is checked to
>>> satisfy QIOs."
>>
>> I am sure that $QIO(W) hits XFC. Else there would not be
>> much point in XFC.
>>
>> The question is whether $QIO(W) get more data read into XFC
>> than asked for by the user. It could but I doubt it.
>
> Consider what I quoted from the fine manual: "system memory software
> cache (that is, XFC) is checked to satisfy QIOs." What would it mean to
> read from cache to "satisfy" a QIO other than there may be more data
> already in the cache than has been explicitly asked for by the user?

The usual reason for finding in cache is that the item has been
read before.

But maybe it does read ahead so that the previous chunk having
been read before is enough.

Arne

On 11/7/2023 9:52 PM, Jake Hamby (Solid State Jake) wrote:
> On Tuesday, November 7, 2023 at 6:17:28 PM UTC-8, Craig A. Berry wrote:
>> On 11/7/23 6:04 PM, Arne Vajhøj wrote:
>>> On 11/7/2023 5:44 PM, Craig A. Berry wrote:
>>>> On 11/6/23 6:18 PM, Arne Vajhøj wrote:
>>>>> But at least for $QIO(W) then I would be very surprised if it did. It is
>>>>> from before VIOC/XFC so originally it did not have anywhere to
>>>>> store read ahead data. VMS engineering could have changed
>>>>> behavior when VIOC/XFC was introduced. But I doubt it.
>>>>
>>>> Are you saying that you think merely using $QIO bypasses XFC? If so,
>>>> how do you think SHOW MEM/CACHE can give you "Total QIOs"? And note
>>>> this from the performance management manual page 72:
>>>> "I/O service can be optimized at the application level by using RMS
>>>> global buffers to share caches among processes. This method offers the
>>>> benefit of satisfying an I/O request without issuing a QIO; whereas
>>>> system memory software cache (that is, XFC) is checked to satisfy QIOs."
>>>
>>> I am sure that $QIO(W) hits XFC. Else there would not be
>>> much point in XFC.
>>>
>>> The question is whether $QIO(W) get more data read into XFC
>>> than asked for by the user. It could but I doubt it.
>> Consider what I quoted from the fine manual: "system memory software
>> cache (that is, XFC) is checked to satisfy QIOs." What would it mean to
>> read from cache to "satisfy" a QIO other than there may be more data
>> already in the cache than has been explicitly asked for by the user?
>>
>> If you're talking about snooping to predict what might be read next and
>> cache it, it looks like that's an attribute of the volume and of XFC
>> itself and doesn't have anything to do with the I/O API in use:
>>
>> https://wiki.vmssoftware.com/VCC_READAHEAD
>
> This thread has been very educational. I wasn't thinking through the implications of a virtual block data cache that's integrated with the filesystem. The VSI wiki page for the V8.4-2L3 release does a better job of explaining the benefits of the features than anything else I've found:
>
> https://wiki.vmssoftware.com/V8.4-2L3
>
> "The Extended File Cache (XFC) is a virtual block data cache provided with OpenVMS for Integrity servers. Similar to the Virtual I/O Cache, the XFC is a clusterwide, file system data cache. Both file system data caches are compatible and coexist in the OpenVMS Cluster. The XFC improves I/O performance with the following features that are not available with the virtual I/O cache:
>
> Read-ahead caching
> Automatic resizing of the cache
> Larger maximum cache size
> No limit on the number of closed files that can be cached
> Control over the maximum size of I/O that can be cached
> Control over whether cache memory is static or dynamic
> XFC caching attributes of volume can be dynamically modified eliminating the need to dismount the volume."

So VIOC (6.0 - 7.2) did not read ahead but XFC (7.3-) does.

My doubt was wrong.

Arne

On 2023-11-08 01:23, Arne Vajhøj wrote:
> On 11/7/2023 11:27 AM, Johnny Billquist wrote:
>> On 2023-11-07 01:18, Arne Vajhøj wrote:
>>> On 11/6/2023 6:31 AM, Johnny Billquist wrote:
>>>> Read ahead is something that the system can easily do both for
>>>> normal I/O and memory mapped I/O. It's just a question of
>>>> speculative reads assuming some pattern by the program. Most
>>>> commonly that you are reading files sequentially from start to finish.
>>>
>>> $QIO(w) and $IO_PERFORM(W) could.
>>>
>>> But at least for $QIO(W) then I would be very surprised if it did. It is
>>> from before VIOC/XFC so originally it did not have anywhere to
>>> store read ahead data. VMS engineering could have changed
>>> behavior when VIOC/XFC was introduced. But I doubt it.
>>>
>>> $IO_PERFORM(W) maybe. But I think the spirit is still
>>> "do exactly what the developer asked for and nothing more".
>>
>> I'd say memory mapped I/O falls in the exact same category here.
>
> Not exact.
>
> $QIO(W) and $IO_PERFORM(W) read means read these X bytes
> now and write means write these X bytes now.
>
> $CRMPSC and memory access read means read at least
> these X bytes now and write means write these X bytes
> either when convenient or when explicit flushed/deleted.

Of course. But I was talking/thinking in the context of read ahead.

But you could also say that with QIO, it's "read these X bytes now",
while with MMAP, it will be read these X bytes when I try to access
them. As for writing back, with QIO, it's "write these X bytes now", but
with MMAP it's a question of write when the kernel wants/needs. There is
no real write request.

QIO would normally run through disk caches, so read ahead is very
possible to happen. But for sure, there is no guarantee. Same story with
MMAP, except I doubt it would run through any disk cache. But you could
possibly have the memory subsystem perform read aheads. But at the same
time, that would risk causing a bad memory pressure, with a negative impact.

Johnny

On 2023-11-08 03:00, Dan Cross wrote:
> In article <uidpd1$6s2$4@news.misty.com>,
> Johnny Billquist <bqt@softjar.se> wrote:
>> On 2023-11-04 15:14, Dan Cross wrote:
>>>>> [snip]
>>>>> Consider the problem of a per-core queue with work-stealing;
>>>>> the specifics of what's in the queue don't matter so much as the
>>>>> overall structure of the problem: items in the queue might
>>>>> represent IO requests, or they may represent runnable threads,
>>>>> or whatever. Anyway, a core will usually process things on
>>>>> its own local queue, but if it runs out of things to do, it
>>>>> may choose some victim and steal some work from it.
>>>>> Conventionally, this will involve everyone taking locks on
>>>>> these queues, but that's ok: we expect that work stealing is
>>>>> pretty rare, and that usually a core is simply locking its own
>>>>> queue, which will be an uncontended write on a cacheline it
>>>>> already owns. In any event, _most of the time_ the overhead
>>>>> of using a "lock" will be minimal (assuming relatively simply
>>>>> spinlocks or MCS locks or something like that).
>>>>
>>>> I generally agree with everything you posted. But I think it's
>>>> unfortunate that you bring in cache lines into this, as it's somewhat
>>>> incorrect to talk about "owning" a cache line, and cache lines are not
>>>> really that relevant at all in this context.
>>>
>>> This is an odd thing to say. It's quite common to talk about
>>> core ownership of cache lines in both MESI and MOESI, which are
>>> the cache coherency protocols in use on modern x86 systems from
>>> both Intel and AMD, respectively. Indeed, the "O" in "MOESI" is
>>> for "owned" (https://en.wikipedia.org/wiki/MOESI_protocol).
>>
>> I think we're talking past each other.
>
> Yes. See below.

:-)

And yes, I know how the cache coherency protocols work. Another thing
that was covered already when I was studying at University.

>>> Cache lines and their ownership are massively relevant in the
>>> context of mutual exclusion, atomic operations, and working on
>>> shared memory generally.
>>
>> You are then talking about it in the sense that if a CPU writes to
>> memory, and it's in the cache, then yes, you get ownership properties
>> then/there. Primarily because you are not immediately writing back to
>> main memory, and other CPUs are allowed to then hold read-only copies. I
>> sortof covered that exact topic further down here, about either
>> invalidate or update the caches of other CPUs. And it also holds that
>> other CPUs cannot freely write or update those memory cells when another
>> CPU holds a dirty cache about it.
>
> Well, no; in the protocols in use on x86, if you have exclusive
> access to a cache line, in either the exclusive or modified
> state, then any other cache's copy of that line is invalidated.

Yes.

> MOESI augments this by allowing sharing of dirty data via the
> OWNED state, allowing for cache-to-cache updates.

Yes. But it only transitions into owned state when you write to it, and
other CPUs have the data in their caches as well, and when it is not
written back to main memory at that point.

>> But before the CPU writes the data, it never owns the cache line. So it
>> don't make sense to say "uncontended write on a cacheline it already
>> owns". Ownership only happens when you do the write. And once you've
>> written, you own it.
>
> This ignores the context; see what I wrote above.
>
> To recap, I was hypothesizing a multiprocessor system with
> per-CPU work queues with work stealing. In such a system, an
> implementation may be to use a spinlock for each CPU's queue: in
> the rare cases where one wants to steal work, one must lock some
> other CPU's queue, _BUT_, in the usual scenario when the per-CPU
> queue is uncontended, the local worker will lock the queue,
> remove an item from it, unlock the queue, do some work, _and
> then repeat_. Note that once it acquires the lock on its queue
> the CPU will own the corresponding cacheline; since we assume
> work stealing is rare, it is likely _it will still own it on
> subsequent iterations of this loop._ Hence, making an
> uncontended write on a cache line it already owns; here, it owns
> it from the last time it made that same write.

That would assume that the cache has not been written back. Which is
likely if we talk about a short time after last updating the lock, but
rather unlikely most of the time.

This boils down to patterns and timing (obviously). I believe that spin
locks are hit hard when you are trying to get a lock, but once you have
it, you will not be touching that thing for quite a while, and it will
quickly go out of cache.

If you are a CPU trying to grab something from another CPU, with a spin
lock held by that other CPU, the spin lock mutex will most likely not
sit in the owners cache. So the other CPU will be hitting it, getting
the value and it gets into the cache. Might be several CPUs as well.
They'll get the value in the cache. Cached value will be flagged as
shared. Noone will have it as owned. The owning CPU then tries to
release the lock, at which time it also access the data, writes it, at
which point the other CPUs will still have it in shared, and the owning
CPU gets it as owned. Other CPUs then try to get the lock, so they all
start kicking the owning CPU cache, in order to get the data comitted to
main memory, so they can obtain ownership, and grab the lock. One of
them will succeed, the others again end up with a shared cache state.
The one CPU that managed to grab the lock will now be the owner, and all
other CPUs will hit it for the cached data, and eventuall it will be
written to memory, and dropped from the owners cache, since the owner is
not actually working on that data.

Cache lines are typically something like 128 bytes or so, so even though
locality means there is some other data around, the owning CPU is
unlikely to care about anything in that cache line, but that is
speculation on my part.

The really bad thing is if you have several spin locks in the same cache
line...

But now I tried to become a little more technical. ;-)

But also maybe we don't need to kick this around any moew. Seems like
we're drifting. I think we started out with the question of I/O
performance, and in this case specifically by using multiple threads in
VMS, and how Unix compatible layers seem to not get much performance,
which seems is no surprise to either of us, while VMS own primitives can
deliver fairly ok performance.

Beyond that, I'm not sure if we are arguing about something much, or
basically nitpicking. :-)

>>>> But that's all there is to it. Now, it is indeed very costly if you have
>>>> many CPUs trying to spin-lock on the same data, because each one will be
>>>> hitting the same memory, causing a big pressure on that memory address.
>>>
>>> More accurately, you'll be pushing the associated cache line
>>> through a huge number of state transitions as different cores
>>> vye for exclusive ownership of the line in order to write the
>>> lock value. Beyond a handful of cores, the generated cache
>>> coherency traffic begins to dominate, and overall throughput
>>> _decreases_.
>>>
>>> This is of paramount importance when we start talking about
>>> things like synchronization primitives, which are based on
>>> atomic updates to shared memory; cache-inefficient algorithms
>>> simply do not scale beyond a handful of actors, and why things
>>> like MCS locks or CHM locks are used on many-core machines.
>>> See, for example:
>>> https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf
>>
>> Yes. This is the scaling problem with spinlocks. Cache coherency starts
>> becoming costly. Having algorithms or structures that allow locking to
>> not be localized to one address is an important piece to help alleviate it.
>
> Not just address, but _cache lines_, which is why this the topic
> is so important. Multiple simultaneous writers to multiple
> memory locations in the same cache line can lead to contention
> due to false sharing.

That is true. Cache lines is really the smallest denominator here. I
should take care about putting that correctly.
It don't help if you have some clever algorithm that spreads the lock
out over multiple addresses, if they all hit the same cache line.

On 2023-11-09, Johnny Billquist <bqt@softjar.se> wrote:
> On 2023-11-09 17:50, Dan Cross wrote:
>> In article <uig3nn$2ke$2@news.misty.com>,
>> Johnny Billquist <bqt@softjar.se> wrote:
>>> On 2023-11-08 03:00, Dan Cross wrote:
>>>> [snip]
>>>> Yes. See below.
>>>
>>> :-)
>>>
>>> And yes, I know how the cache coherency protocols work. Another thing
>>> that was covered already when I was studying at University.
>>
>> Cool. MESI wasn't presented until 1984, so you must have seen
>> it pretty early on.
>
> I think I was looking at it in 1995 (what made you think I would have
> looked at it close to 1984? How old do you think I am??? :) ). My
> professor was specifically focused on CPU caches. He was previously the
> chief architect for high-end server division at SUN (Erik Hagersten if
> you want to look him up).
> I didn't even start at University until 1989.
>

That makes you a lot younger than I thought you were, given your interest
in RSX, which (along with the PDP-11 itself) was pretty much obsolete by
that point. IOW, I certainly thought you were old enough to qualify for
a Senior citizen's travel pass... :-)

What got you interested in RSX in that case ?

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

John Dallman <jgd@cix.co.uk> wrote:
> In article <uic1su$mief$1@dont-email.me>, arne@vajhoej.dk (Arne Vajhøj)
>> I would expect a CS degree to give knowledge of about 3-5 languages.

In 1974 for the one-year Computer Science Part II at Cambridge (they didn’t
think there was enough to learn about Computers to fill 3 years!), we were
assumed to have learned Fortran in whatever Part I we had done (Natural
Sciences for me).

We were then taught (or expected to learn for practicals) the basics of:
BCPL, Algol W (Algol 60), ML/1 (macros), IBM 370 assembler, PDP7 assembler,
Pascal, Algol68, COBOL, PL/1, LISP, Prolog, and SNOBOL (text processing).

Note that C was mentioned, but not used - BCPL was the equivalent systems
language used in Cambridge at that time, and was a primary influence on the
birth of C.

That range of languages taught the underlying concepts of computing and I
subsequently had little difficulty in learning what I needed of C, PDP11
assembler, VAX macro, SQL, Java, Python, JavaScript etc.

Regards,

--
Paul at the paulhardy.net domain

On 2023-11-10 14:32, Simon Clubley wrote:
> On 2023-11-09, Johnny Billquist <bqt@softjar.se> wrote:
>> On 2023-11-09 17:50, Dan Cross wrote:
>>> In article <uig3nn$2ke$2@news.misty.com>,
>>> Johnny Billquist <bqt@softjar.se> wrote:
>>>> On 2023-11-08 03:00, Dan Cross wrote:
>>>>> [snip]
>>>>> Yes. See below.
>>>>
>>>> :-)
>>>>
>>>> And yes, I know how the cache coherency protocols work. Another thing
>>>> that was covered already when I was studying at University.
>>>
>>> Cool. MESI wasn't presented until 1984, so you must have seen
>>> it pretty early on.
>>
>> I think I was looking at it in 1995 (what made you think I would have
>> looked at it close to 1984? How old do you think I am??? :) ). My
>> professor was specifically focused on CPU caches. He was previously the
>> chief architect for high-end server division at SUN (Erik Hagersten if
>> you want to look him up).
>> I didn't even start at University until 1989.
>>
>
> That makes you a lot younger than I thought you were, given your interest
> in RSX, which (along with the PDP-11 itself) was pretty much obsolete by
> that point. IOW, I certainly thought you were old enough to qualify for
> a Senior citizen's travel pass... :-)
>
> What got you interested in RSX in that case ?

I was playing with computers way before I started at University. When I
started in the Gymnasium in Sweden (1982), we shared one PDP-11/70
running RSTS/E between four schools. Having a multiuser system, and
being able to communicate with people in other places were really cool,
and I was a big fan of RSTS/E. (Never got into PCs because of this.)
And this all, of course, led to computer clubs, and I got involved with
one that had a PDP-11/40 on which we eventually got RSX up and running.
And I just found that there were things in RSX that I found nicer than
in RSTS/E, so for my playing around, I start switching more and more
into RSX. And then I got into VMS pretty naturally from there. Worked at
DEC for a while, and eventually started at University (where they were
running DEC-20s), and of course yet again a computer club. This one had
a PDP-8/I, but soon got a PDP-11/34. And me being the person around who
was most experienced with that architecture, I sortof started running
more PDP-11 stuff and RSX again, at after that it's mostly been what
I've been doing for fun.

Johnny

On Thursday, November 9, 2023 at 4:10:13 PM UTC-8, Jake Hamby (Solid State Jake) wrote:
> [snip]

I figured out a perfect resource for OpenVMS I/O performance: the WASD source code. That's 25 years of optimization for VMS, right? :)

As I mentioned in another thread, a professor and a student at my university (Cal Poly, Pomona, 1990s) were really interested in DCE (or at least in DFS, the distributed filesystem built on DCE RPC), and they were philosophically opposed to the campus IT department, who were firmly in the DEC/VMS camp, despite how much money they were sending DEC in licensing and support fees. It "just worked", as far as they were concerned. The Internet was the future and the Internet ran on UNIX, not VMS.

I distinctly remember one of them scoffing one day about how the VMS admins were bragging about the OSU web server they'd set up for students and faculty to put up home pages, and how great it was, and how there was even a second Web server for VMS called WASD.

"OSU? WASD? Who ever heard of those Web servers? They can't be any good. What a terrible OS that can't just run Apache."

That was the gist of the complaint. So I always get a chuckle whenever I'm reminded that WASD is still around and still being developed, even with relatively few users. Sadly, I got an internal compiler error trying to build the latest WASD 12.10 code with the native compilers:

CC/OPTIMIZE=(LEVEL=4,TUNE=HOST)/ARCH=HOST/NAMES=(AS_IS,SHORT)/FLOAT=IEEE/IEEE=DENORM/REPOSITORY=[.X86_64.CXX_REPOSITORY]/L_DOUBLE=64/FIRST=[.X86_64.OBJ]FIRST.H/OBJECT=[.UTILS.OBJ_X86_64]httpdmon_geolocate.obj/DEFINE=(HTTPDMON_GEOLOCATE=1,GEOLOCATE_OBJECT=1) [.utils]httpdmon.c
assert error: expression = isa<X>(Val) && "cast<Ty>() argument of incompatible type!", in file /llvm$root/include/llvm-project-10/llvm/include/llvm/Support/Casting.h at line 264
%SYSTEM-F-OPCCUS, opcode reserved to customer fault at PC=FFFF8300097367DF, PS=0000001B
%TRACE-F-TRACEBACK, symbolic stack dump follows
image module routine line rel PC abs PC
DECC$SHR SIGNAL.C;1 #20739 00000000801C97DF FFFF8300097367DF
DECC$SHR ABORT.C;1 #2967 000000008009643B FFFF83000960343B
DECC$SHR 0 000000008039B779 FFFF830009908779
DECC$COMPILER [.src]g2l_entrysymbol.cxx cast<llvm::Function, llvm::Value>
#175 0000000001A1E2C1 0000000001A1E2C1
DECC$COMPILER [.src]g2l_entrysymbol.cxx dwarf
#394 0000000000AD057B 0000000000AD057B
DECC$COMPILER [.src]g2l_symbol.cxx convertSymbol
#828 0000000000A4993A 0000000000A4993A
DECC$COMPILER [.src]g2l_module.cxx convertDeclarations
#1554 0000000000A473B7 0000000000A473B7
DECC$COMPILER [.src]g2l_module.cxx convertModule
#1165 0000000000A44603 0000000000A44603
DECC$COMPILER [.src]g2l_module.cxx G2L_COMPILE_MODULE
#619 0000000000A43181 0000000000A43181
DECC$COMPILER GEM_CO.BLI;1 GEM_CO_COMPILE_MODULE
#3223 0000000000000A54 00000000006D8844
DECC$COMPILER COMPILE.C;1 gemc_be_master
#103704 00000000004238BE 00000000004238BE
DECC$COMPILER COMPILE.C;1 gem_xx_compile
#102915 0000000000422597 0000000000422597
DECC$COMPILER GEM_CP_VMS.BLI;1 GEM_CP_MAIN
#2447 000000000000384E 00000000006CC23E
DECC$COMPILER 0 0000000000AD36A4 0000000000AD36A4
DECC$COMPILER 0 00000000021887AD 00000000021887AD
PTHREAD$RTL 0 000000008004122C FFFF83000950922C
PTHREAD$RTL 0 0000000080002316 FFFF8300094CA316
0 FFFF8300081FC0A6 FFFF8300081FC0A6
DCL 0 000000008006778B 000000007ADEB78B
%TRACE-I-LINENUMBER, Leading '#' specifies a source file record number.
%TRACE-I-END, end of TRACE stack dump
%MMS-F-ABORT, For target [.UTILS.OBJ_X86_64]httpdmon_geolocate.obj, CLI returned abort status: %X10000434.
%MMS-F-ABORT, For target BUILD, CLI returned abort status: %X10EE8034.

It's too bad because I was hoping to see how it compared to Apache on VMS, using the Siege benchmark. I copied the test params from Phoronix Test Suite, which repeatedly gets a simple .html file that loads a .png file, both about 4K in size. Apache on VMS isn't terrible. I got 1174 trans/sec with 10 clients (3.43 MB/sec thoroughput) which seems decent enough for such small files. I'm using Linux on the host VM as the client and it actually runs out of sockets if you don't enable keepalive and you do more than 64000 requests. Closed TCP sockets spend a little time in TIME_WAIT so you can run through them quickly.

Despite not being able to run an optimized WASD, looking at the source code confirmed some details. QIO is slightly faster than RMS, once you've found and opened the file. I'll likely reference the file I/O code for default buffer and copy sizes.

The TCP/IP code had some surprises. TCP/IP send/receive is limited to 65535 bytes by the $QIO interface (for disk I/O, the IOSB has space for a return value of up to 2^32-1 bytes, but for mailboxes and sockets, it only has 16 bits to return a data length), so it turns out that you get optimum results sending/receiving in chunks of the highest multiple of the TCP max segment size that fits in 65535 bytes.

In addition, WASD testing revealed that the VSI TCP/IP stack sets its own TCP send buffer size to that value (highest multiple of the TCP MSS below 65536), but testing revealed the best server performance came from changing the TCP send buffer size to twice that value.

One annoyance for me for porting libuv is that the TCP/IP stack supports QIO send/receive with scatter/gather buffers (readv()/writev()), which you see often in socket code for putting headers and payloads in different places.. But there's no equivalent for disk I/O, and also you have to read/write on 512-byte block boundaries. So for reads/writes that start from an unaligned offset in the file, I'll have to use a small buffer to read the block and then memcpy() the portion that the user asked for. For writes, I'll have to read that block, then overlay it with the portion they want to overwrite, then write the new block and the rest of the write. In the worst case, someone's writing multiple small chunks of data, misaligned, to a file using an iovec list, and I'll have to coalesce them into 512-byte or larger chunks. I have to keep reminding myself that at least it isn't scatter/gather on the disk side, but only the in-memory copying that could be very fragmented, at least from the perspective of handling an individual async file I/O request.

In article <uij9oc$st3$1@news.misty.com>,
Johnny Billquist <bqt@softjar.se> wrote:
>On 2023-11-09 17:50, Dan Cross wrote:
>> In article <uig3nn$2ke$2@news.misty.com>,
>> Johnny Billquist <bqt@softjar.se> wrote:
>>> On 2023-11-08 03:00, Dan Cross wrote:
>>>> [snip]
>>>> Yes. See below.
>>>
>>> :-)
>>>
>>> And yes, I know how the cache coherency protocols work. Another thing
>>> that was covered already when I was studying at University.
>>
>> Cool. MESI wasn't presented until 1984, so you must have seen
>> it pretty early on.
>
>I think I was looking at it in 1995 (what made you think I would have
>looked at it close to 1984? How old do you think I am??? :) ).

*cough* Uh, ahem...sorry.... *cough*

>My
>professor was specifically focused on CPU caches. He was previously the
>chief architect for high-end server division at SUN (Erik Hagersten if
>you want to look him up).
>I didn't even start at University until 1989.

Gosh, I think like some other folks I just ASSumed you were
older given your PDP-11 interests. Apologies!

>[snip]
>But yes, it's not impossible. We're all down to speculations here.

Agreed.

>> That's are assumptions that may or may not hold.
>
>I think it's a fairly safe assumption that once you have acquired the
>spin lock, you will not be hitting the cell than contains the state of
>the spin lock. There is absolutely no point in continuing hitting that
>one after this point.

Well, you have to release the lock, which will be a store, which
will touch the line. If you've got a very short critical
section, say just removing something from a list, which is a
handful of instructions, it is very unlikely that the line
holding the lock will be evicted before the end of the critical
section.

>And it's also safe to assume that we will be
>running through a bunch of code once we do have acquired the lock.

I don't think that's a safe assumption at all, especially for a
spin lock: minimizing the length of the critical section should
absolutely be a goal.

>Since
>that's the whole point of the lock - once you have it you can proceed in
>doing the stuff you want exclusive access in order to do.
>
>So that leaves the assumption that this will flush that line out. But I
>think that one is also fairly safe to say that it will happen within a
>short future. Caches, after all, only contains a rather limited amount
>of data, compared to the full memory, or what memory your code hits.

This is true, but again, we're all speculating.

>>> The owning CPU then tries to
>>> release the lock, at which time it also access the data, writes it, at
>>> which point the other CPUs will still have it in shared, and the owning
>>> CPU gets it as owned.
>>
>> Hey now? Seems like most spinlock releases on x86 are simply
>> going to be a memory barrier followed by a store. That'll push
>> the line in the local into MODIFIED and invalidate all other
>> caches.
>
>Why would it invalidate other caches?

Because that's what the protocol says it must do? :-)

>It could just push the change into
>their caches as well. At which point the local CPU would have "owned"
>and others "shared".

Well, no.... Even in MOESI, a write hit puts an OWNED cache
line into MODIFIED state, and a probe write hit puts the line
into INVALID state from any state. A probe read hit can move a
line from MODIFIED into OWNED (presumably that's when it pushes
its modified contents to other caches).

>But yes, it could just also invalidate the others,
>and move to "modified". Both are equally correct states.

Yup; I agree.

>>> Other CPUs then try to get the lock, so they all
>>> start kicking the owning CPU cache, in order to get the data comitted to
>>> main memory, so they can obtain ownership, and grab the lock. One of
>>> them will succeed, the others again end up with a shared cache state.
>>
>> Actually, immediately after one succeeds, the others will be in
>> INVALID state until they're read again, then they may or may not
>> be in EXCLUSIVE or SHARED; depending on how they are
>> implemented.
>
>You seem to assume that updates never gets pushed from the cache on one
>CPU to the others, but always just do an invalidate. It's possible to do
>either. Exactly what any specific implementation does on the other hand
>I have no idea.

Well, that is what the protocols both say that they do, though I
suppose it is theoretically possible that MOESI could avoid it.

>>> Cache lines are typically something like 128 bytes or so, so even though
>>> locality means there is some other data around, the owning CPU is
>>> unlikely to care about anything in that cache line, but that is
>>> speculation on my part.
>>
>> Cache line size on current x86 processors is 64 bytes, but yeah.
>
>I can't even keep track of that. It changes over time anyway, and is not
>even CPU specific. It's an implementation detail for the memory
>subsystem. :)

What's worse is that there are big.LITTLE ARM configurations
that have different cache line sizes for the different CPUS in
the same SoC complex!

>>> But now I tried to become a little more technical. ;-)
>>>
>>> But also maybe we don't need to kick this around any moew. Seems like
>>> we're drifting. I think we started out with the question of I/O
>>> performance, and in this case specifically by using multiple threads in
>>> VMS, and how Unix compatible layers seem to not get much performance,
>>> which seems is no surprise to either of us, while VMS own primitives can
>>> deliver fairly ok performance.
>>
>> Well getting back to that.... One of the things that I found
>> rather odd was that that discussion seems to conflate macro- and
>> micro-level optimizations in an odd way. I mean, it went from
>> talking about efficient ways to retrieve data from a secondary
>> storage device that is orders of magnitude slower than the CPU
>> to atomic operations and reducing mutex contention, which seems
>> like for most IO-bound applications will be in the noise.
>
>True.
>
>>> Beyond that, I'm not sure if we are arguing about something much, or
>>> basically nitpicking. :-)
>>
>> This is true. :-) It's fun, though! Also, I've found that not
>> understanding how this stuff works in detail can have really
>> profound performance implications. Simply put, most programmers
>> don't have good intuition here.
>
>Maybe I should tell about the time when I worked at a compane where we
>were making network switching/routing and did our own hardware, and were
>very careful about exactly where each byte of incoming packets ended up
>so that all the data we were interested in were all sitting in the same
>cache line, to get the most speed out of it all...

Nice.

>>>>>>> (And then we had the PDP-11/74, which had to implement cache coherency
>>>>>>> between CPUs without any hardware support...)
>>>>>>
>>>>>> Sounds rough. :-/
>>>>>
>>>>> It is. CPU was modified to actually always step around the cache for one
>>>>> instruction (ASRB - used for spin locks), and then you manually turn on
>>>>> and off cache bypass on a per-page basis, or in general of the CPU,
>>>>> depending on what is being done, in order to not get into issues of
>>>>> cache inconsistency.
>>>>
>>>> This implies that stores were in a total order, then, and
>>>> these uncached instructions were serializing with respect to
>>>> other CPUs?
>>>
>>> The uncached instruction is basically there in order to be able to
>>> implement a spin lock that works as you would expect. Once you have the
>>> lock, then you either deal with data which is known to be shared, in
>>> which case you need to run with cache disabled, or you are dealing with
>>> data you know is not shared, in which case you can allow caching to work
>>> as normal.
>>>
>>> No data access to shared resources are allowed to be done without
>>> getting the lock first.
>>
>> Sure. But suppose I use the uncached instructions to implement
>> a lock around a shared data structure; I use the uncached instr
>> to grab a lock, I modify (say) a counter in "normal" memory with
>> a "normal" instruction and then I use the uncached instruction
>> to release the lock. But what about the counter value? Is its
>> new value --- the update to which was protected by the lock ---
>> immediately visible to all other CPUs?
>
>Like I said - if you are dealing with shared data, even after you get
>the lock, you then need to turn off the cache while working on it. So
>basically, such updates would immediately hit main memory. And any reads
>of that data would also be done with cache disabled, so you get the
>actual data. So updates always immediately visible to all CPUs.

On 2023-11-11 16:06, Dan Cross wrote:
> In article <uij9oc$st3$1@news.misty.com>,
> Johnny Billquist <bqt@softjar.se> wrote:
>> On 2023-11-09 17:50, Dan Cross wrote:
>>> In article <uig3nn$2ke$2@news.misty.com>,
>>> Johnny Billquist <bqt@softjar.se> wrote:
>>>> On 2023-11-08 03:00, Dan Cross wrote:
>>>>> [snip]
>>>>> Yes. See below.
>>>>
>>>> :-)
>>>>
>>>> And yes, I know how the cache coherency protocols work. Another thing
>>>> that was covered already when I was studying at University.
>>>
>>> Cool. MESI wasn't presented until 1984, so you must have seen
>>> it pretty early on.
>>
>> I think I was looking at it in 1995 (what made you think I would have
>> looked at it close to 1984? How old do you think I am??? :) ).
>
> *cough* Uh, ahem...sorry.... *cough*

Well, it's kindof funny. :-)

>> My
>> professor was specifically focused on CPU caches. He was previously the
>> chief architect for high-end server division at SUN (Erik Hagersten if
>> you want to look him up).
>> I didn't even start at University until 1989.
>
> Gosh, I think like some other folks I just ASSumed you were
> older given your PDP-11 interests. Apologies!

Admittedly I'm not young anymore either. I started playing around on
PDP-11s when they were still kindof widespread.

>>>> The owning CPU then tries to
>>>> release the lock, at which time it also access the data, writes it, at
>>>> which point the other CPUs will still have it in shared, and the owning
>>>> CPU gets it as owned.
>>>
>>> Hey now? Seems like most spinlock releases on x86 are simply
>>> going to be a memory barrier followed by a store. That'll push
>>> the line in the local into MODIFIED and invalidate all other
>>> caches.
>>
>> Why would it invalidate other caches?
>
> Because that's what the protocol says it must do? :-)

If you want to move it to MODIFIED, then yes, you need to invalidate all
other CPU caches. But there is no good reason to do that in general.

To quote the wikipedia article:

"Owned
This cache is one of several with a valid copy of the cache line, but
has the exclusive right to make changes to it—other caches may read but
not write the cache line. When this cache changes data on the cache
line, it must broadcast those changes to all other caches sharing the
line. The introduction of the Owned state allows dirty sharing of data,
i.e., a modified cache block can be moved around various caches without
updating main memory. The cache line may be changed to the Modified
state after invalidating all shared copies, or changed to the Shared
state by writing the modifications back to main memory. Owned cache
lines must respond to a snoop request with data."

Note the "when the cache changes the data on the cache line, it must
broadcast those changes to all other caches sharing the line".

So basically - no. If you have a cache in owned state, and you change
the content, you already have the data modified, but you own it, and any
changes you broadcast to anyone else who also have the data in their
cache. All others have the cache line in SHARED state, so they cannot
modify it.

But eventually you need to flush it, at which point it goes back to main
memory, and your copy is invalidated. Others still have it shared. Of
course, someone else might want to try and write, at which point the
ownership needs to move over there. More handshaking...

Basically, OWNED is to allow sharing of dirty cache without it being in
main memory. You're the one who even reminded me about it. :D

>> It could just push the change into
>> their caches as well. At which point the local CPU would have "owned"
>> and others "shared".
>
> Well, no.... Even in MOESI, a write hit puts an OWNED cache
> line into MODIFIED state, and a probe write hit puts the line
> into INVALID state from any state. A probe read hit can move a
> line from MODIFIED into OWNED (presumably that's when it pushes
> its modified contents to other caches).

No. OWNED means you already modified it. You can modify it additional
times if you want to. It don't change anything in cache state.

But anyone else who have that same line in SHARED needs to either be
invalidated or updated. But as noted above, the normal thing is to update.

You don't get to OWNED state until you actually do modify the cache.
It't not that modifying the cache moves out out of OWNED. It moves you
INTO OWNED.

>>>>>>>> (And then we had the PDP-11/74, which had to implement cache coherency
>>>>>>>> between CPUs without any hardware support...)
>>>>>>>
>>>>>>> Sounds rough. :-/
>>>>>>
>>>>>> It is. CPU was modified to actually always step around the cache for one
>>>>>> instruction (ASRB - used for spin locks), and then you manually turn on
>>>>>> and off cache bypass on a per-page basis, or in general of the CPU,
>>>>>> depending on what is being done, in order to not get into issues of
>>>>>> cache inconsistency.
>>>>>
>>>>> This implies that stores were in a total order, then, and
>>>>> these uncached instructions were serializing with respect to
>>>>> other CPUs?
>>>>
>>>> The uncached instruction is basically there in order to be able to
>>>> implement a spin lock that works as you would expect. Once you have the
>>>> lock, then you either deal with data which is known to be shared, in
>>>> which case you need to run with cache disabled, or you are dealing with
>>>> data you know is not shared, in which case you can allow caching to work
>>>> as normal.
>>>>
>>>> No data access to shared resources are allowed to be done without
>>>> getting the lock first.
>>>
>>> Sure. But suppose I use the uncached instructions to implement
>>> a lock around a shared data structure; I use the uncached instr
>>> to grab a lock, I modify (say) a counter in "normal" memory with
>>> a "normal" instruction and then I use the uncached instruction
>>> to release the lock. But what about the counter value? Is its
>>> new value --- the update to which was protected by the lock ---
>>> immediately visible to all other CPUs?
>>
>> Like I said - if you are dealing with shared data, even after you get
>> the lock, you then need to turn off the cache while working on it. So
>> basically, such updates would immediately hit main memory. And any reads
>> of that data would also be done with cache disabled, so you get the
>> actual data. So updates always immediately visible to all CPUs.
>
> Oh, I understand now: I had missed that if you wanted the data
> protected by the lock to be immediately visible to the other
> CPUs you had to disable caching (which, I presume, would flush
> cache contents back to RAM). Indeed, it's impressive that they
> were able to do that back then.

The PDP-11 never had write-back caching. Only write-through. So no need
to flush as such.
But you want to bypass (as well as invalidate) what's in there, in case
physical memory holds something else.

Johnny

On 11/10/2023 8:20 PM, Johnny Billquist wrote:
> On 2023-11-10 14:32, Simon Clubley wrote:
>> On 2023-11-09, Johnny Billquist <bqt@softjar.se> wrote:
>>> On 2023-11-09 17:50, Dan Cross wrote:
>>>> In article <uig3nn$2ke$2@news.misty.com>,
>>>> Johnny Billquist  <bqt@softjar.se> wrote:
>>>>> On 2023-11-08 03:00, Dan Cross wrote:
>>>>>> [snip]
>>>>>> Yes.  See below.
>>>>>
>>>>> :-)
>>>>>
>>>>> And yes, I know how the cache coherency protocols work. Another thing
>>>>> that was covered already when I was studying at University.
>>>>
>>>> Cool.  MESI wasn't presented until 1984, so you must have seen
>>>> it pretty early on.
>>>
>>> I think I was looking at it in 1995 (what made you think I would have
>>> looked at it close to 1984? How old do you think I am??? :) ). My
>>> professor was specifically focused on CPU caches. He was previously the
>>> chief architect for high-end server division at SUN (Erik Hagersten if
>>> you want to look him up).
>>> I didn't even start at University until 1989.
>>>
>>
>> That makes you a lot younger than I thought you were, given your interest
>> in RSX, which (along with the PDP-11 itself) was pretty much obsolete by
>> that point. IOW, I certainly thought you were old enough to qualify for
>> a Senior citizen's travel pass... :-)
>>
>> What got you interested in RSX in that case ?
>
> I was playing with computers way before I started at University. When I
> started in the Gymnasium in Sweden (1982), we shared one PDP-11/70
> running RSTS/E between four schools. Having a multiuser system, and
> being able to communicate with people in other places were really cool,
> and I was a big fan of RSTS/E. (Never got into PCs because of this.)
> And this all, of course, led to computer clubs, and I got involved with
> one that had a PDP-11/40 on which we eventually got RSX up and running.
> And I just found that there were things in RSX that I found nicer than
> in RSTS/E, so for my playing around, I start switching more and more
> into RSX. And then I got into VMS pretty naturally from there. Worked at
> DEC for a while, and eventually started at University (where they were
> running DEC-20s), and of course yet again a computer club. This one had
> a PDP-8/I, but soon got a PDP-11/34. And me being the person around who
> was most experienced with that architecture, I sortof started running
> more PDP-11 stuff and RSX again, at after that it's mostly been what
> I've been doing for fun.
>

Sometimes the story comes out even stranger. My first contact with
a PDP-11 (actually LSI-11/02) was in 1980 int he form of the dreaded
Terak. Did UCSD-Pascal and RT-11. I liked it and shortly thereafter
I actually had some at home.
My next experience came when I was a contractor doing pre-sales bid
work. We were bidding a big Air Force contract that included the
requirement to talk to the PDP-11 running RSX. Because I had worked
with PDP-11's in the past I got the task. While did get it all set
up and met the requirement I had not been impressed with RSX.
I didn't get serious with PDP-11's again until about 1989. By then I
was working at a University. They were given a gift of 4 PDP-11 systems
by the company that did the Highlights children's magazine. Turned
out all the University wanted from the donation was the RA disks.
Rather than see them go to the dump I took them. No RA's but they did
have RL drives and controllers. And a couple of the packs had RSTS on
them. I really liked RSTS and have worked with both RSTS and RT-11
ever since.
So, actually, I didn't get serious about the PDP-11 until it was on the
way out. Being replaced by the VAX which I was also not overly
impressed with. Of course, by then I was a Unix Guru so that was where
most of my professional time went.

So, age really has little to do with it.

bill

On 2023-11-10, Johnny Billquist <bqt@softjar.se> wrote:
>
> I was playing with computers way before I started at University. When I
> started in the Gymnasium in Sweden (1982), we shared one PDP-11/70
> running RSTS/E between four schools. Having a multiuser system, and
> being able to communicate with people in other places were really cool,
> and I was a big fan of RSTS/E. (Never got into PCs because of this.)
> And this all, of course, led to computer clubs, and I got involved with
> one that had a PDP-11/40 on which we eventually got RSX up and running.
> And I just found that there were things in RSX that I found nicer than
> in RSTS/E, so for my playing around, I start switching more and more
> into RSX. And then I got into VMS pretty naturally from there. Worked at
> DEC for a while, and eventually started at University (where they were
> running DEC-20s), and of course yet again a computer club. This one had
> a PDP-8/I, but soon got a PDP-11/34. And me being the person around who
> was most experienced with that architecture, I sortof started running
> more PDP-11 stuff and RSX again, at after that it's mostly been what
> I've been doing for fun.
>

In my case, the decisive moment was when I was 14 when I entered
upper secondary school.

My parents had moved house over the summer into a new school catchment
area and I couldn't take both technical drawing (IIRC) and computer
science at the new secondary school.

I knew nothing about either of the subjects and had to choose on the
spot which one I wanted to take. I choose computer science. Within
a few weeks I was utterly hooked and the rest is history. :-)

[In those days, if you showed the level of interest I rapidly did in
school, your interest was assumed to be both genuine and benign. As a
result, thanks to the teaching staff, I was able to explore the equipment
I had access to in a way that you would _never_ be allowed to these days.
I probably learnt a _lot_ more outside of the classroom than I did in it.]

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 11/9/2023 1:51 PM, Johnny Billquist wrote:
> How old do you think I am??? :)

I guess we assumed that you were born when Gustav Vasa was
king.

:-) :-) :-)

Arne

On 2023-11-13, Arne Vajhøj <arne@vajhoej.dk> wrote:
> On 11/9/2023 1:51 PM, Johnny Billquist wrote:
>> How old do you think I am??? :)
>
> I guess we assumed that you were born when Gustav Vasa was
> king.
>

In fairness to Johnny, I didn't think he was _that_ old, but I did wonder
if he was around when Sweden decided to object to Carsten Anker's
independence plans next door. :-)

>:-) :-) :-)
>

Likewise. :-) :-)

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 2023-11-13 19:14, Simon Clubley wrote:
> On 2023-11-13, Arne Vajhøj <arne@vajhoej.dk> wrote:
>> On 11/9/2023 1:51 PM, Johnny Billquist wrote:
>>> How old do you think I am??? :)
>>
>> I guess we assumed that you were born when Gustav Vasa was
>> king.
>>
>
> In fairness to Johnny, I didn't think he was _that_ old, but I did wonder
> if he was around when Sweden decided to object to Carsten Anker's
> independence plans next door. :-)
>
>> :-) :-) :-)
>>
>
> Likewise. :-) :-)

:-P to both of you. :-D

Johnny

On Tue, 2023-11-14 at 10:36 +0100, Johnny Billquist wrote:
> On 2023-11-13 19:14, Simon Clubley wrote:
> > On 2023-11-13, Arne Vajhøj <arne@vajhoej.dk> wrote:
> > > On 11/9/2023 1:51 PM, Johnny Billquist wrote:
> > > >                              How old do you think I am??? :)
> > >
> > > I guess we assumed that you were born when Gustav Vasa was
> > > king.
> > >
> >
> > In fairness to Johnny, I didn't think he was _that_ old, but I did
> > wonder
> > if he was around when Sweden decided to object to Carsten Anker's
> > independence plans next door. :-)
> >
> > > :-) :-) :-)
> > >
> >
> > Likewise. :-) :-)
>
> :-P to both of you. :-D

Plenty of greybeards on here :-D
--
Tactical Nuclear Kittens

[sorry for the delayed response; I was out of pocket for a few
days doing some volunteer outdoors conservation work....]

In article <uiovnc$td7$1@news.misty.com>,
Johnny Billquist <bqt@softjar.se> wrote:
>On 2023-11-11 16:06, Dan Cross wrote:
>> In article <uij9oc$st3$1@news.misty.com>,
>> Johnny Billquist <bqt@softjar.se> wrote:
>>> On 2023-11-09 17:50, Dan Cross wrote:
>>>> In article <uig3nn$2ke$2@news.misty.com>,
>>>> Johnny Billquist <bqt@softjar.se> wrote:
>>>>> On 2023-11-08 03:00, Dan Cross wrote:
>>>>>> [snip]
>>>>>> Yes. See below.
>>>>>
>>>>> :-)
>>>>>
>>>>> And yes, I know how the cache coherency protocols work. Another thing
>>>>> that was covered already when I was studying at University.
>>>>
>>>> Cool. MESI wasn't presented until 1984, so you must have seen
>>>> it pretty early on.
>>>
>>> I think I was looking at it in 1995 (what made you think I would have
>>> looked at it close to 1984? How old do you think I am??? :) ).
>>
>> *cough* Uh, ahem...sorry.... *cough*
>
>Well, it's kindof funny. :-)

Glad you took it in the spirit it was offered. :-D

>>>>> The owning CPU then tries to
>>>>> release the lock, at which time it also access the data, writes it, at
>>>>> which point the other CPUs will still have it in shared, and the owning
>>>>> CPU gets it as owned.
>>>>
>>>> Hey now? Seems like most spinlock releases on x86 are simply
>>>> going to be a memory barrier followed by a store. That'll push
>>>> the line in the local into MODIFIED and invalidate all other
>>>> caches.
>>>
>>> Why would it invalidate other caches?
>>
>> Because that's what the protocol says it must do? :-)
>
>If you want to move it to MODIFIED, then yes, you need to invalidate all
>other CPU caches. But there is no good reason to do that in general.

Perhaps not, but that's how the protocol works.

>To quote the wikipedia article:
>
>"Owned
>This cache is one of several with a valid copy of the cache line, but
>has the exclusive right to make changes to it—other caches may read but
>not write the cache line. When this cache changes data on the cache
>line, it must broadcast those changes to all other caches sharing the
>line. The introduction of the Owned state allows dirty sharing of data,
>i.e., a modified cache block can be moved around various caches without
>updating main memory. The cache line may be changed to the Modified
>state after invalidating all shared copies, or changed to the Shared
>state by writing the modifications back to main memory. Owned cache
>lines must respond to a snoop request with data."
>
>Note the "when the cache changes the data on the cache line, it must
>broadcast those changes to all other caches sharing the line".

Hmm, in this case, I think the wikipedia article may be wrong,
or at least misleading. How would a CPU know what other CPUs
are sharing the cache line? A write to an OWNED line (by the
owner) will generate a WrReq and move the line into OWNED; any
other CPU holding the line will get a probe WrReq and transition
the line to INVALID. But the transition to OWNED only happens
from MODIFIED, and won't happen unless the cache snoops a RdReq,
in which case it can supply the value on the cache bus.

>So basically - no. If you have a cache in owned state, and you change
>the content, you already have the data modified, but you own it, and any
>changes you broadcast to anyone else who also have the data in their
>cache. All others have the cache line in SHARED state, so they cannot
>modify it.

No, sorry, that's just not how the protocol works. Here's a
decent reference:
https://inst.eecs.berkeley.edu/~cs61c/su18/disc/11/Disc11Sol.pdf

>But eventually you need to flush it, at which point it goes back to main
>memory, and your copy is invalidated.

Writing to main memory doesn't invalidate _your_ cache copy, it
just puts it into SHARED state.

>Others still have it shared. Of
>course, someone else might want to try and write, at which point the
>ownership needs to move over there. More handshaking...

The difference with MESI here is that a probe read hit on a
MODIFIED cache line transitions the line on the owning core to
OWNED and allows the other cache to receive data from the owning
CPU's cache. A subsequent write to an OWNED line will
transition the line to MODIFIED and invalidate anyone who has it
in SHARED state until a subsequent read request is probed.

>Basically, OWNED is to allow sharing of dirty cache without it being in
>main memory. You're the one who even reminded me about it. :D

Yes, but you only get to OWNED after you probe a read request.
Preemptively pushing to other caches seems unsporting; how would
you know that the other cache line would actually be _used_?
Putting additional contention on another CPUs cache is mean. :-)

>>> It could just push the change into
>>> their caches as well. At which point the local CPU would have "owned"
>>> and others "shared".
>>
>> Well, no.... Even in MOESI, a write hit puts an OWNED cache
>> line into MODIFIED state, and a probe write hit puts the line
>> into INVALID state from any state. A probe read hit can move a
>> line from MODIFIED into OWNED (presumably that's when it pushes
>> its modified contents to other caches).
>
>No. OWNED means you already modified it. You can modify it additional
>times if you want to. It don't change anything in cache state.

I'm afraid it does. See the above linked document.

>But anyone else who have that same line in SHARED needs to either be
>invalidated or updated. But as noted above, the normal thing is to update.
>
>You don't get to OWNED state until you actually do modify the cache.
>It't not that modifying the cache moves out out of OWNED. It moves you
>INTO OWNED.

No. You only get into OWNED from MODIFIED if you probe a read
request.

>[snip]
>The PDP-11 never had write-back caching. Only write-through. So no need
>to flush as such.
>But you want to bypass (as well as invalidate) what's in there, in case
>physical memory holds something else.

That makes sense.

- Dan C.