Comments (8)
You probably want to take a look at
#938 (comment)
and
#939
from cs431.
let atomic = self.buckets.get(index,guard); let shared = atomic.load(SeqCst,guard); let cursor = Cursor::new(atomic,shared);The
V
inCursor::new()
is a generic parameter. For the split ordered list we instantiate it withMaybeUninit<V>
.
Copied from #938.
In the code above, atomic
is a reference to a pointer in self.buckets
, not a reference to a next
pointer of the node before shared
. The Cursor
API seems like it assumes that cursor.prev
is a reference to a next
pointer of a node in the list, and violating this assumption might lead to unexpected behaviors.
For example, if this cursor
is later used to insert a new node, cursor.prev
might be CASed to a pointer to a new node, changing the pointer in the growable array, which clearly isn't what we want.
from cs431.
In the code above, atomic is a reference to a pointer in self.buckets, not a reference to a next pointer of the node before shared.
atomic
is a reference to a node of self.list
, not to a pointer in the growable array; this is blocked at the type level, which returns a Atomic<T>
, not Atomic<Segment<T>>
. If that is what self.buckets.get()
returned, one has an incorrect growable array implementation.
The intention of the Cursor::new()
API is to literally use it like the example code I gave you. For example, see:
https://github.com/kaist-cp/cs431/blob/main/src/lockfree/list.rs#L288-L290
It simple loads the head pointer which has type Atomic<Node<K,V>>
, essentially same as atomic
, and creates a cursor saving those two values. There is nothing special with the head node here, and using a &'g Atomic<Node<K,V>>
that references any node in the list will do, including atomic
.
from cs431.
In the code above, atomic is a reference to a pointer in self.buckets, not a reference to a next pointer of the node before shared.
atomic
is a reference to a node ofself.list
, not to a pointer in the growable array; this is blocked at the type level, which returns aAtomic<T>
, notAtomic<Segment<T>>
. If that is whatself.buckets.get()
returned, one has an incorrect growable array implementation.
I thought atomic
is not "a reference to a node of self.list
", but "a reference to a Atomic<Node>
that points to a node of self.list
". If atomic
was "a reference to a node of self.list
", its type must've been &Node
. GrowableArray<T>
internally stores Atomic<T>
s, and give access to them through get()
.
In the Cursor
insert API, we create a new node, make the node point to cursor's curr
, and CAS the cursor's prev
to point to our new node. This makes sense when we have a cursor created from List::head()
, since the cursor's prev
is part of the list. Using atomic
, returned from GrowableArray<Node>::get()
, as a cursor's prev
is thus going to cause a problem, since a CAS to atomic
will not change self.list
, but corrupt self.buckets
.
from cs431.
BTW, at least on my implementation, this doesn't make the hash table buggy, since even if lookup_buckets()
returns a Cursor
with an invalid prev
, we never insert()
a new node into the cursor without a find_XX()
before it, and find_XX()
s will fix the prev
if they encounter a "curr
node with a valid tag, but has a smaller key than the target". Our curr
is pointing to the bucket sentinel, which is never removed (thus have a valid tag) and is guaranteed to have a smaller key than the target. (We calculate the bucket index to be smaller than the target node anyway.)
TL;DR: This problem won't cause the code to fail.
from cs431.
The return type for 'self.buckets.get()' for the split ordered list is '&Atomic<Node<K,MaybeUninit>', which means the returned value is a reference to the next field of some node in 'self.list'. I'm really not sure why you keep on saying using it will cause corruption of the array, which can only happen if it's an internal (children) node of the growable array, which it isn't.
from cs431.
This is my current understanding on GrowableArray<T>
:
A GrowableArray<T>
doesn't manage the value of type T
, but only stores a pointer to it. Leaf Segment<T>
s store Atomic<T>
pointers that point to the value of type T
. On get()
calls, the API returns a reference to the Atomic<T>
stored in leaf node segments. This is why GrowableArray<T>
doesn't have 'insert()' calls: the 'get()' call already returns a reference to an element (of type Atomic<T>
of its leaf segment, and users are expected to modify the pointer to point to a data of type T
. (If it returned Atomic<T>
, users wouldn't be able to modify the array at all.)
In my understanding, GrowableArray<Node>
can't possibly return references to the next field of a node in self.list
, because it is not designed to do so. GrowableArray<Node>
is designed to point to Node
s, not Atomic<Node>
s. If someone wanted to have self.buckets
point to the next field of some node in self.list
, they would've used self.buckets
of type GrowableArray<Atomic<Node>>
.
from cs431.
Ah ok I see your point. I agree on your points and think that the current Cursor
API is a bit fragile. I think the reason it's ok for this is due to the usage of sentinel nodes that won't be tagged and stuff, but in general it should be fixed. I'll try to fix it ASAP.
from cs431.
Related Issues (20)
- [Question] I get VALID?=timeout with full score log HOT 4
- [Lecture] Suggestion on teaching promising semantics HOT 1
- Optional Q&A session on June 5th (Wed)
- [Question] Understanding of access hazard & ABA hazard HOT 1
- Server rebooting scheduled (Jun 5, Wed, 10pm~) HOT 1
- [Question] zip is not installed on server HOT 2
- gg.kaist.ac.kr down for preparing for the final exam HOT 1
- [Question] find_harris_herlihy_shavit relaxed load for tag HOT 6
- [Question] Timeout on growable_array stress_concurrent with cargo_asan HOT 2
- [Question] Hazard Pointers: is it safe to protect a pointer to invalid memory? HOT 5
- [Question] Code lines for maintaining the invariants of stack/queue HOT 1
- [Question] About the problem of 2022 Fall HOT 2
- [Question] ordering in stack push for maintaining invariant HOT 1
- Final claim session on June 17th (Mon) HOT 4
- [Question] HW 7 reason for having atomicUsize type in hazard field HOT 2
- [Question] [HW7] Failed Basic Tests in hazard.rs HOT 3
- [Question] HW7 Dropping the Hazard Bag HOT 3
- [Question] Partial Points on HW7 HOT 1
- [Question] err happend when run cargo run hello_server in terminal HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cs431.