nt-list
by Colin Finck <[email protected]>
Provides compatible, type-safe, and idiomatic Rust implementations of the Windows NT Linked Lists, known as LIST_ENTRY and SINGLE_LIST_ENTRY.
In Action
Debugging a Rust application in WinDbg and using the !list extension to traverse a doubly linked list. A testament to the compatibility between nt-list and LIST_ENTRY.
Details
Singly and doubly linked lists of this format are fundamental data structures widely used in Windows itself and in drivers written for Windows. In the case of a doubly linked list, Windows defines a LIST_ENTRY structure with forward and backward pointers to other LIST_ENTRY structures. LIST_ENTRY is then embedded into your own element structure. Check the relevant Microsoft documentation for more details on linked lists in Windows.
This design exhibits several properties that differ from textbook linked list implementations:
- A single element can be part of multiple lists (by having multiple
LIST_ENTRYfields). - YOU are responsible for pushing only elements of the same type to a list. Without any type safety, the C/C++ compiler cannot prevent you from adding differently typed elements to the same list.
- Links point to the
LIST_ENTRYfield of an element and not to the element itself. YOU need to retrieve the corresponding element structure usingCONTAINING_RECORD, and YOU are responsible for all parameters passed to that macro.
The nt-list crate introduces type safety for these lists, taking away some responsibility from the user and moving it to the compiler. Additionally, it offers an idiomatic Rust interface similar to that of LinkedList and Vec.
Example
Creating a linked list with nt-list boils down to these three steps:
- You define an empty enum to identify your list (for type safety when pushing elements), and derive either
NtList(doubly linked list) orNtSingleList(singly linked list). - You define your element structure, declare an entry as
#[boxed]if desired, and deriveNtListElement. - You call
newof the respective list implementation with the element structure and empty enum as type parameters.
All of this taken together looks like:
#[derive(NtSingleList)]
enum MyList {}
#[derive(Default, NtListElement)]
#[repr(C)]
struct MyElement {
#[boxed]
entry: NtSingleListEntry<Self, MyList>,
value: i32,
}
fn test() {
let mut list = NtBoxingSingleListHead::<MyElement, MyList>::new();
list.push_back(MyElement {
value: 42,
..Default::default()
});
for element in list.iter() {
println!("{}", element.value);
}
}
Check the module-level documentation of list for a doubly linked list example.
no_std support
The crate is no_std-compatible and therefore usable from firmware-level code up to user-mode applications.
To support heap allocations in NtBoxingListHead and NtBoxingSingleListHead, the crate depends on the alloc library. If you want to use the crate in a pure no_std environment without heap allocations, include it with default-features = false to disable the default alloc feature.
License
This crate is licensed under either of
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
33 Sep 25, 2022
3 May 4, 2022
1 Jan 20, 2022
160 Dec 29, 2022
58 Dec 18, 2022
88 Jan 2, 2023
3 Oct 20, 2022
7 Mar 1, 2023
4 Dec 26, 2022
2 Dec 20, 2022
4 Jan 9, 2023
5 Apr 30, 2023
51 Oct 13, 2022
126 Dec 30, 2022
153 Dec 27, 2022
741 Jan 5, 2023
296 Dec 31, 2022
49 Dec 9, 2022
2.1k Jan 6, 2023