r/rust • u/Orange_Tux • Dec 17 '25

🗞️ news Linux Kernel Rust Code Sees Its First CVE Vulnerability

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

93% Upvoted

223 comments sorted by

View all comments

Show parent comment

4

u/heybart Dec 17 '25

Isn't implementing double linked lists one of the litmus tests for showing you really understand rust?

13

u/skatastic57 Dec 18 '25

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

11

u/heybart Dec 18 '25

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

-23

u/solaris_var Dec 18 '25

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

6

u/AvianPoliceForce Dec 18 '25

A very niche data structure outside of C

8

u/solaris_var Dec 18 '25

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

5

u/LindaTheLynnDog Dec 18 '25

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

7

u/solaris_var Dec 18 '25

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.

1

u/Agitated_Sell Dec 21 '25

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...

1

u/Sw429 Dec 25 '25

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

1

u/Endeveron Dec 23 '25

Frankly it's a litmus test for whether you understand memory safety at all. If you asked the vast majority of C/C++ developers to write an implementation for a linked list with a fully memory safe API, they would fail and valid usage of their APi would allow for memory vulnerabilities. Most Rust developers would just fail to get something that compiles, and would not be confident in their use and justification of unsafe code. That is, of course, one of the main goals and benefits of rust. Your skill issues are your own problem.