Linux内核进展：页组管理、多代LRU替换算法及Rust语言支持的技术探讨与实践资源-CSDN文库

版权申诉

198 浏览量 2025-01-25 16:26:29 上传评论收藏 346KB PDF 举报

资源推荐

资源详情

资源评论

By Jonathan Corbet
January 20, 2022
The kernel radar: folios, multi-generational LRU,
and Rust
The kernel community is a busy place, so it is not even remotely possible to write
full-length articles about everything that is going on. Other topics may be of
interest, but not require a longer treatment. The answer is a collection of short topics
covering developments that are on the radar; the selection this time around includes folios, the multi-
generational LRU, and Rust in the kernel.
A folio update
Folios have been an active topic since they were first covered here less than one year ago. A folio, recall, is just
a container for a struct page that is guaranteed not to be a tail page. It can thus be used to refer to memory, in
units of a single page or larger, in a way that is more type-safe and requiring fewer run-time checks than when
working directly with page structures. After some extensive discussion, the first set of folio patches was merged
for the 5.16 kernel.
A large change of that nature to the memory-management subsystem naturally leads to fears of regressions, but
the work in 5.16 appears to have been relatively problem-free. So 5.17 saw another round of folio-related
changes, mostly focused on the page cache (which caches file data). In current kernels, the page cache holds,
unsurprisingly, pages, but the 4KB page size used on most systems is often far too small to be efficiently
managed. When dealing with files of anything but the smallest size, there is value in caching larger chunks at a
time. The 5.17 conversion of the page cache to use folios is intended, among other things, to allow the use of
"large folios" (a name chosen because the more descriptive "multi-page folios" was a little too long). Large
folios might be huge pages, but they don't have to be limited to the huge-page sizes supported by the CPU; the
plan is to support any folio size, as long as it is a power of two.
The 5.17 work adds the machinery to support large folios in the page cache, the low-level filesystem-support
code, and in the XFS filesystem, but does not actually start using them yet. As Matthew Wilcox said in his pull
request: "there may still be places I've overlooked which still have page size assumptions". So the coming
development cycle will, presumably, focus on finding any such places so that the transition can happen in 5.18.
Meanwhile, the more adventurous among us can enable large folios in 5.17 and help find the remaining sharp
edges.
The multi-generational LRU
Another significant memory-management change that has been under development over the last year is the
multi-generational LRU, which reworks how the kernel decides which pages to evict when memory is tight.
Current kernels use a two-queue system, one each for pages deemed "active" and "inactive". Pages move
between the queues based on accesses; when memory is needed, pages are reclaimed off the end of the inactive
queue. The multi-generational work generalizes this setup into a larger number of queues, a change that
seemingly improves the kernel's ability to identify the pages that are unlikely to be needed in the near future.
When Yu Zhao posted the sixth version of this patch set in early January, he added a request for review and a
verdict as to whether it could be merged for 5.17. That sparked a long discussion on the state of this work. As
part of that discussion, Michal Hocko (who also did a lot of detailed review of the patches) repeated a theme

that has been heard with previous postings: that it would be better to see this work as a series of incremental
changes rather than a big addition of new reclaim mechanism:
Changes in the reclaim path are paved with failures and reverts and fine tuning on top of existing
fine tuning. The difference from your patchset is that they tend to be much much smaller and go
incremental and therefore easier to review.
Jesse Barnes responded that an incremental series might be worse in this case:
I understand the desire for an "incremental approach that gets us from A->B". In the abstract it
sounds great. However, with a change like this one, I think it's highly likely that such a path would
be littered with regressions both large and small, and would probably be more difficult to reason
about than the relatively clean design of MGLRU. On top of that, I don't think we'll get the kind of
user feedback we need for something like this *without* merging it.
Linus Torvalds responded to Barnes, saying that this work "is worth going with". Hocko didn't disagree with
Barnes, but did note that there are a lot of things needing fixing before the code could be merged in any case.
Zhao, meanwhile, has been actively trying to get supporters of this work to post to the list in favor of its
inclusion. Those who responded include Holger Hoffstätte, Shuang Zhai ("the performance improvement is
fabulous"), Suleiman Souhlal ("Android on ChromeOS has been using MGLRU for a while now, with great
results"), Sofia Trinh, Donald Carr, and Oleksandr Natalenko.
There is clearly some interest in getting this work merged; it is just as clearly not in the cards for 5.17, though.
Normally one would expect that a change this fundamental could take a long time yet to get in; given the
pressure and the approval from Torvalds, though, it could happen a bit more quickly this time. Merging for 5.18
still seems optimistic, but sometime in 2022 could be a real possibility.
Rust for Linux
The project to make it possible to develop kernel modules in the Rust programming language continues to move
forward; the third version of the Rust-support patch set was posted on January 17. A number of changes had
been made to keep up with the Rust community and to get this work closer to ready for inclusion.
This version of the patch set supports (and thus requires) the recent 1.58 release of the compiler. The build
system is now able to determine automatically whether a suitable Rust toolchain is available for building and, if
something is missing, it will tell the developer what is needed. The cover letter notes that a couple of the
unstable Rust features required for kernel work are becoming stable in near-future compiler releases. There is,
however, still a discouragingly long list of required unstable features.
The series itself starts by increasing the maximum length of symbols that can be managed in the "kallsyms"
mechanism. It seems that the name-mangling used by Rust can expand names considerably, to the point that 255
characters is not enough to store some names. Developers will not normally need to see the mangled names, but
they will show up in kallsyms and may be surprising. Another preliminary step is to add C helper functions for a
long list of things that already look like functions in the kernel — readb() or kmap(), for example — that are
actually macros or are inlined. Those cannot be called directly from Rust, so they need to be turned into proper
functions first.
Most of the Rust code itself currently appears in two crates. The first, called alloc, deals with memory
allocation. The Rust language wasn't built with the idea that code might need to continue when a memory
allocation fails; instead, the normal result is an immediate crash. Since crashing in kernel code is considered to
be impolite, a modified allocator that can handle failures is required. As a Rust developer would expect, it
returns a Result object that contains either a pointer to the allocated memory or an error indication, depending
on what happened. Evidently the work to support fallible allocations is meant to go into the upstream Rust
library, so the kernel's version of this crate may eventually be able to go away.

Index entries for this article

Kernel Development tools/Rust

Kernel Memory management/Folios

Kernel Memory management/Page replacement algorithms

The other big crate is called kernel; it contains the rest of the impedance-matching code that makes kernel APIs

look like proper Rust interfaces. These provide interfaces for char devices, the clock framework, file structures,

file_operations vectors, memory-mapped I/O functions, mutexes, spinlocks, and more. A surprising amount of

code is dedicated to the implementation of generic linked lists.

All told, it represents a lot of work toward making it possible to write kernel code in Rust. It is quite a bit of

code that, at some point, is going to need to be more widely exercised if it is to progress in useful directions.

That, of course, would be helped by getting this support into the mainline kernel where more developers can

look at and work with it. Torvalds indicated at the 2021 Maintainers Summit that he expected to merge this

work, but there is no indication of when that might happen. The timing is likely to come down to Torvalds and

when he thinks that the time has come to open the door to this new language.

(Log in to post comments)

The kernel radar: folios, multi-generational LRU, and Rust

Posted Jan 20, 2022 22:49 UTC (Thu) by developer122 (guest, #152928) [Link]

Yeah, as I've heard Brian Cantrill say during a twitter space podcast thing, Rust and it's compiletime ownership-

checks really doesn't work well with the concept of linked lists. After all "if you have b-trees, why would you

use anything else?" And Rust's ownership checking makes (generically implemented) b-trees easy where as in

C or other languages they tend to end up being a horrible buggy mess.

Reply to this comment

Rust

Posted Jan 20, 2022 23:29 UTC (Thu) by tialaramex (subscriber, #21167) [Link]

The stability list isn't TOO bad once you consider it standing back a few paces.

I count 17 items, 4 are cfg() parameters, to switch off features from the allocator and, in one case, the core

Rust library†. That latter is worth a moment's thought: Rust says you can format floating point numbers.

Linux, of course, would very much rather you didn't use floating point numbers at all. So, Rust-for-Linux

wants to tell the core library that we aren't going to be formatting any floating point numbers, blow up code

that tries to do that, that's not valid Linux code. However, ultimately you _could_ do this surgery by hand and

in effect "fork" the core library, especially if you knew a real fix was coming later.

2 more are -Z compiler flags. Rust's compiler has flags marked as not being stable with a Z prefix. It's not as

though the kernel has never taken a dependency on compiler specific flags before, but clearly having a stable

flag is better because it's a social contract not to move this particular feature unexpectedly.

Some of the others have community momentum behind them because they're things most Rust users want,

GATs and more const are in that category. If Rust for Linux didn't engage with the main Rust community at

all for 12 months, those things have traction and will make progress anyway. On the other hand, there are few

applications outside the kernel for some of the compiler internals stabilization that Rust for Linux wants, if

they never did this I for example, writing userspace code, would never ever notice.

It overall certainly means I don't expect to be running a Linux kernel with Rust in it in 2022 on my PC. But it

also doesn't feel insurmountable, I could imagine reading an LWN piece before the end of the year about the

剩余10页未读，继续阅读

评论收藏

内容反馈

版权申诉

mounter625

粉丝: 1621
资源: 217

Linux 内核进展：页组管理、多代LRU替换算法及Rust语言支持的技术探讨与实践

最新资源

Linux 内核进展：页组管理、多代LRU替换算法及Rust语言支持的技术探讨与实践

操作系统 程实现请求分页存储管理页面Optimal、FIFO、LRU置换算法

存贮层次模拟器FIFO、LRU等替换算法

Rust的 CLOCK-Pro 缓存替换算法_rust_代码_下载

页面替换算法（实现了最佳置换算法，随机置换算法，LRU算法，FIFO算法，CLOCK算法）

页面替换算法———LRU算法

页面替换算法opt+fifo+lru+clock

编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法

计算机系统结构LRU替换算法的源码绝对可以用。

lru.rar_LRU_LRU page replacement_lru 算法_页面替换_页面替换算法

Linux内核中的预取算法.docx

用C++实现LRU页面置换算法

实验--编程实现请求分页存储管理页面Optimal、FIFO、LRU置换算法.docx

LRU算法存储器管理

操作系统实验-请求分页存储管理页面Optimal、FIFO、LRU调度算法

2-3 linux 内核页管理和lru list locking 优化1

操作系统 课程设计 页面置换算法FIFO和 LRU

页面替换算法FIFO+最优+clock+LRU+随机

java实现LRU虚拟内存替换算法.zip

页面替换算法（fifo lru的实现）

LRU页面置换算法

c语言实现的LRU算法

JAVA实现FIFO、LRU、OPT页面置换算法，有界面

linux内核内存管理

操作系统之LRU算法（java）（csdn）————程序.pdf

lru算法实验报告

电子科大Linux内核技术课程

LRU算法 lru算法

页面置换算法LRU（模拟页面管理）

linux aarch64架构libreoffice安装包

RocketMQ 可视化工具 Dashboard下载

最新资源

操作系统程实现请求分页存储管理页面Optimal、FIFO、LRU置换算法

操作系统课程设计页面置换算法FIFO和 LRU