Hacker News Reader

Hacker News

Comment by souprock | Hacker News Reader

Parent Full thread

souprock

The use of LL/SC for atomics is a common mistake. It makes replay debuggers like rr impossible to implement.

View on HN

For anyone confused like me, see https://en.wikipedia.org/wiki/Load-link/store-conditional

I am surprised that the link you posted works…

Why?

Presumably because the title of the page contains a slash, which isn’t escaped in the url. Some Webservers might have interpreted as a directory.

Wikipedia is not made up of a series of flat files that have the same paths as you see in the URL. The URL layout is controlled by MediaWiki and it's free to do whatever it wants with the slashes. After rewriting, the URL looks like:

  https://en.wikipedia.org/w/index.php?title=Load-link%2Fstore-conditional

You can actually visit that if you like.

It has a slash in it; I would have expected that to need escaping.

Slashes are not special in URLs (unlike #, & and semicolon). It's only servers that parse them as path separators.

See section 3.3 "Path" in RFC 3986: https://tools.ietf.org/html/rfc3986#section-3.3

> A path consists of a sequence of path segments separated by a slash ("/") character

It continues like this: "Use of the slash character to indicate hierarchy is only required when a URI will be used as the context for relative references [...] The path segments "." and ".." [...] are intended for use at the beginning of a relative-path reference (Section 4.2) to indicate relative position within the hierarchical tree of names. [...] Aside from dot-segments in hierarchical paths, a path segment is considered opaque by the generic syntax."

As long as Wikipedia doesn't use relative paths it is not a problem to have slashes in the URL.

RFC 3986 says one thing, but what the HTTP protocol allows servers to do and they actually implement is another thing.

HTTP protocol RFC pretty explicitly says that the Request-URI transmitted is a "path" and refers to URI RFC to define "path". There is really no ambiguity here, HTTP as a protocol expects resources to be organized as an hierarchy and accessed via a path, which is delimited by "/" characters. As such the protocol definitely reserves and assigns special meaning to "/" in paths.

Of course servers are perfectly free to do whatever they want, there is no HTTP police to stop them.

Wikipedia doesn't.

LL/SC is superior to CAS in that a modification to the memory will be detected even though the value has since been set back to the original value. This avoids the ABA problem.

No. CAS is superior to LL/SC. There is no possible undetected modification to the memory. That's how atomic operations work. That's the whole point of an atomic operation. It's atomic.

Botching the code can be done with either mechanism. Don't do that.

This only avoided the ABA problem if the code which is ABA prone is run in-between the LL and SC instruction.

But this is where the problem starts. E.g. for RISC when using LR/SC in a way which prevents ABA your are always losing all forward guarantees and it's totally valid for a implementation to be done in a way which will just never complete in such cases...

Looks like someone read the Wikipedia link posted in a sibling comment ;)

Well, actually, I discovered this when I was playing with implementing a lock free queue in shared memory. I was using singly linked lists; one for the queue and one for the free list. A node would sometimes come back to the queue's head from the free list and mess things up. It's not surprising that this is well known, but I learnt it by doing. :)

Yeah, that's fair, just poking fun at Wikipedia having the exact same thing paraphrased slightly differently ;)

Last I heard, adding a hardware counter for failed SCs may help work around this on ARM–presumably RISC-V could do the same thing here?

Not necessarily, it needs to allow trap on failures.

Reply on news.ycombinator.com