|
|
Log in / Subscribe / Register

Better linked-list traversal in BPF

Better linked-list traversal in BPF

Posted Mar 8, 2024 18:59 UTC (Fri) by atnot (guest, #124910)
In reply to: Better linked-list traversal in BPF by epa
Parent article: Better linked-list traversal in BPF

There's hash tables that do this. But I think in reality that's kind of just otherthinking it. Very few C programs use linked lists for good reasons and want or need any of the very few positive properties of them. It's mostly just used because it's the first thing you learn in school and perhaps more importantly the only datastructure that's easy to implement and use in C without macro hell. That and not nearly enough people tell programmers it's a bad idea.*

* this goes beyond just performance implications but architectural decisions too. One of the "advantages" of linked lists is that list items rarely move once they get created. This inevitably leads to things like structures getting bloated with information really only needed by one user and people stashing long-lived pointers to objects on lists somewhere without really worrying about how long they'll stay valid for, which ossifies into the familiar pointer hell codebase where you're scared of changing anything because something might still be holding a pointer to it and 5% of your CPU time is refcounting. But I digress.


to post comments

Better linked-list traversal in BPF

Posted Mar 9, 2024 15:51 UTC (Sat) by adobriyan (subscriber, #30858) [Link] (1 responses)

How would you structure (pardon the repetition) data structures?

Userspace have a luxury of kernel doing equivalent of vmalloc for their std::vector's, but kernel have to deal with fragmentation.

Better linked-list traversal in BPF

Posted Mar 9, 2024 20:24 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link]

There's no real reason the kernel can't allocate its internal data in a contiguous virtual RAM. It's just that right now the kernel has one simple 1-to-1 mapping.


Copyright © 2026, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds