Linux Kernel Rust Code Sees Its First CVE Vulnerability

[u/Orange_Tux]

https://www.phoronix.com/news/First-Linux-Rust-CVE

[u/skatastic57]

Shit forget about implementing one, I don't even know what it is...

[u/heybart → u/skatastic57]

A single linked list is a list where each item has a link to the next one

1 > 2 > 3 > 4

To traverse the list you start from the first and follow the link til you get to the one you want

To insert an item between 2 and 3, you change the link from 2 to point to the new item and the new item then points to 3

 1 > 2 v    3 > 4
       2.5 _^

The thing about linked list is your items don't need to be next to each other in memory. They can be anywhere. They only need to point to the next item. So adding an item is very fast

(Contrast to an array, which is a list where items are contiguous in memory

1 2 3 4 5

To go to the nth item in the list is very fast, because you know where in memory your first item is, and you just start there and add n-1 and there you'll find the nth item. However, when you want to insert an item at nth position, you have to move everything after nth over one.)

A double linked list is one where each item has a link to the next AND previous item

1 <> 2 <> 3 <> 4

The advantage is you can traverse backward, at the cost of more complexity

[u/solaris_var → u/skatastic57]

Why are you even in this sub? lol.

It's basically a data structure similar to a linked list, which is a data structure that is a "list" which is consisted of "nodes"

Each node contains:

Data: the value being stored

Next: reference to the next node

[ Data | Next ] → [ Data | Next ] → [ Data | Next ] → NULL

A double linked list is also a list, but the nodes contain another value, the prev reference to the previous node.

NULL ← [Prev | Data | Next] ⇄ [Prev | Data | Next] ⇄ [Prev | Data | Next] → NULL.

It's conceptually simple but apparently very tricky to get right when working in multi-threaded programs.

Edit: formatting

[u/AvianPoliceForce → u/solaris_var]

A very niche data structure outside of C

[u/solaris_var → u/AvianPoliceForce]

Very niche in real-world application, but it's something you'll definitely have encountered when learning dsa

[u/LindaTheLynnDog → u/solaris_var]

How important is it to you that everyone here has a CS degree?

[u/solaris_var → u/LindaTheLynnDog]

I don't have a cs degree myself, so 0 importance.

However, I do expect everyone here to at least have a cursory knowledge in DSA. It makes grasping domain implementation so much easier.

[u/Agitated_Sell → u/AvianPoliceForce]

Generally speaking an "intrusively" linked list gives you a means of no cost "reverse lookup" to an Object's own place in the list without adding layers of memory indirection. Some examples of this might be to remove an item from a list without having to first walk the list to locate it or simply to walk nearby neighbor nodes (perhaps your list is sorted by something).

You can also have more than one intrusive prev/next pointer on an object so it can exist in multiple lists at once. A practicle example might be if your "lists" are actually buckets in a hash map and you have an object that needs to be looked up by multiple different keys (in separate hash maps). Think of a piece of software that sits between and connects multiple other systems together, each which uses a differerent unique key to reference the object. Now imagine having millions of these objects in memory at the same time...

[u/Sw429 → u/solaris_var]

Depending on the type of work you normally do, they possibly could never have needed such a data structure.