Adding 16 kb page size to Android

https://android-developers.googleblog.com/2024/08/adding-16-kb-page-size-to-android.html

by mikece • 2 years ago

322 167 2 years ago

android-developers.googleblog.com

monocasa4• 2 years ago

I wonder how much help they had by asahi doing a lot of the kernel and ecosystem work anablibg 16k pages.

RISC-V being fixed to 4k pages seems to be a bit of an oversight as well.

ashkankiani• 2 years ago

It's pretty cool that I can read "anablibg" and know that means "enabling." The brain is pretty neat. I wonder if LLMs would get it too. They probably would.

mrob• 2 years ago

LLMs are at a great disadvantage here because they operate on tokens, not letters.

mrbuttons454• 2 years ago

Until I read your comment I didn't even notice...

evilduck2• 2 years ago

Question I wrote:

I encountered the typo "anablibg" in the sentence "I wonder how much help they had by asahi doing a lot of the kernel and ecosystem work anablibg 16k pages." What did they actually mean?

GPT-4o and Sonnet 3.5 understood it perfectly. This isn't really a problem for the large models.

For local small models:

* Gemma2 9b did not get it and thought it meant "analyzing".

* Codestral (22b) did not it get it and thought it meant "allocating".

* Phi3 Mini failed spectacularly.

* Phi3 14b and Qwen2 did not get it and thought it was "annotating".

* Mistral-nemo thought it was a portmanteau "anabling" as a combination of "an" and "enabling". Partial credit for being close and some creativity?

* Llama3.1 got it perfectly.

im3w1l• 2 years ago

I asked chatgpt and it did get it.

Personally, when I read the comment my brain kinda skipped over the word since it contained the part "lib" I assumed it was some obscure library that I didn't care about. It doesn't fit grammatically but I didn't give it enough thought to notice.

IshKebab3• 2 years ago

Probably wouldn't be too hard to add a 16 kB page size extension. But I think the Svnapot extension is their solution to this problem. If you're not familiar it lets you mark a set of pages as being part of a contiguously mapped 64 kB region. No idea how the performance characteristics vary. It relieves TLB pressure, but you still have to create 16 4kB page table entries.

monocasa4• 2 years ago

Svnapot is a poor solution to the problem.

On one hand it means that that each page table entry takes up half a cache line for the 16KB case, and two whole cache lines in the 64KB case. This really cuts down on the page walker hardware's ability to effectively prefetch TLB entries, leading to basically the same issues as this classic discussion about why tree based page tables are generally more effective than hash based page tables (shifted forward in time to today's gate counts). https://yarchive.net/comp/linux/page_tables.html This is why ARM shifted from a Svnapot like solution to the "translation granule queryable and partially selectable at runtime" solution.

Another issue is the fact that a big reason to switch to 16KB or even 64KB pages is to allow for more address range for VIPT caches. You want to allow high performance implementations to be able to look up the cache line while performing the TLB lookup in parallel, then compare the tag with the result of the TLB lookup. This means that practically only the untranslated bits of the address can be used by the set selection portion of the cache lookup. When you have 12 bits untranslated in a address, combined with 64 byte cachelines gives you 64 sets, multiply that by 8 ways and you get the 32KB L1 caches very common in systems with 4KB page sizes (sometimes with some heroic effort to throw a ton of transistors/power at the problem to make a 64KB cache by essentially duplicating large parts of the cache lookup hardware for that extra bit of address). What you really want is for the arch to be able to disallow 4KB pages like on apple silicon which is the main piece that allows their giant 128LB and 192KB L1 caches.

saagarjha8• 2 years ago

Probably very little, since the Android ecosystem is quite divorced from the Linux one.

nabla9• 2 years ago

Android kernel is a mainstream Linux kernel, with additional drivers, and other functionality.

wren69912• 2 years ago

RV64 has some reserved encoding space in satp.mode so there's an obvious path to expanding the number of page table formats at a later time. Just requires everyone to agree on the direction (common issue with RISC-V).

For RV32 I think we are probably stuck with Sv32 4k pages forever.

twoodfin• 2 years ago

A little additional background: iOS has used 16KB pages since the 64-bit transition, and ARM Macs have inherited that design.

arghwhat3• 2 years ago

A more relevant bit of background is that 4KB pages lead to quite a lot of overhead due to the sheer number of mappings needing to be configured and cached. Using larger pages reduce overhead, in particular TLB misses as fewer entries are needed to describe the same memory range.

While x86 chips mainly supports 4K, 2M and 1G pages, ARM chips tend to support more practical 16K page sizes - a nice balance between performance and wasting memory due to lower allocation granularity.

Nothing in particular to do with Apple and iOS.

jsheard2• 2 years ago

Makes me wonder how much performance Windows is leaving on the table with its primitive support for large pages. It does support them, but it doesn't coalesce pages transparently like Linux does, and explicitly allocating them requires special permissions and is very likely to fail due to fragmentation if the system has been running for a while. In practice it's scarcely used outside of server software which immediately grabs a big chunk of large pages at boot and holds onto them forever.

daghamm2• 2 years ago

IIRC, 64-bit ARM can do 4K, 16K, 64K and 2M pages. But there are some special rules for the last one.

https://documentation-service.arm.com/static/64d5f38f4a92140...

CalChris4• 2 years ago

Armv8-A also supports 4K pages: FEAT_TGran4K. So Apple did indeed make a choice to instead use 16K, FEAT_TGran16K. Microsoft uses 4K for AArch64 Windows.

HumblyTossed• 2 years ago

How is this "additional background"? This was a post by Google regarding Android.

Kwpolska3• 2 years ago

That this isn't the only 4K→16K transition in recent history? Some programs that assumed 4K had to be fixed as part of the transition, this can provide insights for the work required for Android.

carstenhag• 2 years ago

As an android dev: the work hours I spend talking with iOS colleagues is the same as with AND ones. Usually you want to sort of be up to date with the other platform as well.

a1o• 2 years ago

The very first 16 KB enabled Android system will be made available on select devices as a developer option. This is so you can use the developer option to test and fix
once an application is fixed to be page size agnostic, the same application binary can run on both 4 KB and 16 KB devices

I am curious about this. When could an app NOT be agnostic to this? Like what an app must be doing to cause this to be noticeable?

mlmandude• 2 years ago

If you use mmap/munmap directly within your application you could probably get into trouble by hardcoding the page size.

vardump• 2 years ago

For example use mmap and just assume 4 kB pages.

dmytroi• 2 years ago

Also ELF segment alignment, which is defaults to 4k.

bri3d• 2 years ago

Only on Android, for what it's worth; most "vanilla" Linux aarch64 linkers chose 64K defaults several years ago. But yes, most Android applications with native (NDK) binaries will need to be rebuilt with the new 16kb max-page-size.

edflsafoiewq• 2 years ago

jemalloc bakes in page size assumptions, see eg https://github.com/jemalloc/jemalloc/issues/467.

sweeter• 2 years ago

Wine doesn't work on 16 KB page size among other things.

mananaysiempre3• 2 years ago

This seems especially peculiar given Windows has a 64K mapping granularity.

blkhp19• 2 years ago

Why does Wine work just fine on an M-series Mac then?

o11c• 2 years ago

The fundamental problem is that system headers don't provide enough information. In particular, many programs need both "min runtime page size" and "max runtime page size" (and by this I mean non-huge pages).

If you call `mmap` without constraint, you need to assume the result will be aligned to at least "min runtime page size". In practice it is probably safe to assume 4K for this for "normal" systems, but I've seen it down to 128 bytes on some embedded systems, and I don't have much breadth there (this will break many programs though, since there are more errno values than that). I don't know enough about SPARC binary compatibility to know if it's safe to push this up to 8K for certain targets.

But if you want to call `mmap` (etc.) with full constraint, you must work in terms of "max runtime page size". This is known to be up to at least 64K in the wild (aarch64), but some architectures have "huge" pages not much beyond that so I'm not sure (256K, 512K, and 1M; beyond that is almost certainly going to be considered huge pages).

Besides a C macro, these values also need to be baked into the object file and the linker needs to prevent incompatible assumptions (just in case a new microarchitecture changes them)

dotancohen3• 2 years ago

Yes, but the context here is Java or Kotlin running on Android, not embedded C.

Or do some Android applications run embedded C with only a Java UI? I'm not an Android dev.

lanigone2• 2 years ago

you can also do 2M and 1G huge pages on x86, it gets kind of silly fast.

saagarjha8• 2 years ago

Pages sizes are often important to code that relies on low-level details of the environment it’s running in, like language runtimes. They might do things like mark some sections of code as writable or executable and thus would need to know what the granularity of those requests can be. It’s also of importance to things like allocators that hand out memory backed by mmap pages. If they have, say, a bit field for each 16-byte region of a page that has been used that will change in size in ways they can detect.

growse• 2 years ago

If you use a database library that does mmap to create a db file with SC_PAGE_SIZE (4KB) pages, and then upgrade your device to a 16KB one and backup/restore the app, now your data isn't readable.

phh2• 2 years ago

Which is the reason you need to format your data to experiment with 16k

nox101• 2 years ago

I don't know if this fits but I've seen code that allocated say 32 bytes from a function that allocated 1meg under the hood. Not knowing that's what was happening the app quickly ran out of memory. It arguably was not the app's fault. The API it was calling into was poorly designed and poorly named, such that the fact that you might need to know the block size to use the function was in no way indicated by the name of the function nor the names of any of its parameters.

dataflow• 2 years ago

When could an app NOT be agnostic to this

When the app has a custom memory allocator, the allocator might have hardcoded the page size for performance. Otherwise you have to load a static variable (knocks out a cache line you could've used for something else) and then do a multiplication (or bit shift, if you assume power of 2) by a runtime value instead of a shift by a constant, which can be slower.

No idea if Android apps are ever this performance sensitive, though.

lostmsu2• 2 years ago

Not entirely related (except the block size), but I am considering making and standardizing a system-wide content-based cache with default block size 16KB.

The idea is that you'd have a system-wide (or not) service that can do two or three things:

- read 16KB block by its SHA256 (also return length that can be <16KB), if cached

- write a block to cache

- maybe pin a block (e.g. make it non-evictable)

I would be like a block-level file content dedup + eviction to keep the size limited.

Should reduce storage used by various things due to dedup functionality, but may require internet for corresponding apps to work properly.

With a peer-to-peer sharing system on top of it may significantly reduce storage requirements.

The only disadvantage is the same as with shared website caches prior to cache isolation introduction: apps can poke what you have in your cache and deduce some information about you from it.

monocasa4• 2 years ago

I'd probably pick a size greater than 16KB for that. Windows doesn't expose translations less than 64KB in their version of mmap, and internally their file cache works in increments of 256KB. And these were numbers they picked back in the 90s.

treyd2• 2 years ago

I would go for higher than 16K. I believe BitTorrent's default minimum chunk size is 64K, for example. It really depends on the use case in question though, if you're doing random writes then larger chunk sizes quickly waste a ton of bandwidth, especially if you're doing recursive rewrites of a tree structure.

Would a variable chunk size be acceptable for whatever it is you're building?

lostmsu2• 2 years ago

I could feasibly do 2x partitioning. E.g. have caches for 16KB, 32KB, etc provided there's some mechanism to automatically combine/split pieces

devit• 2 years ago

Seems pretty dubious to do this without adding support for having both 4KB and 16KB processes at once to the Linux kernel, since it means all old binaries break and emulators which emulate normal systems with 4KB pages (Wine, console emulators, etc.) might dramatically lose performance if they need to emulate the MMU.

Hopefully they don't actually ship a 16KB default before supporting 4KB pages as well in the same kernel.

Also it would probably be reasonable, along with making the Linux kernel change, to design CPUs where you can configure a 16KB pagetable entry to map at 4KB granularity and pagefault after the first 4KB or 8KB (requires 3 extra bits per PTE or 2 if coalesced with the invalid bit), so that memory can be saved by allocating 4KB/8KB pages when 16KB would have wasted padding.

username81• 2 years ago

Shouldn't there be some kind of setting to change the page size per program? AFAIK AMD64 CPUs can do this.

saagarjha8• 2 years ago

Yes, ARM CPUs can do it too.

fouronnes3• 2 years ago

Could they upstream that or would that require a fork?

mgaunard2• 2 years ago

why does it break userland? if you need to know the page size, you should query sysconf SC_PAGESIZE.

akdev1l• 2 years ago

Assumptions in the software.

Jemalloc is infamous for this: https://github.com/sigp/lighthouse/issues/5244

Dwedit• 2 years ago

Emulating a processor with 4K size pages becomes much higher performance if you can use real addresses directly.

fweimer• 2 years ago

It should not break userland. GNU/Linux (not necessarily Android though) has supported 64K pages pretty much from the start because that was the originally page size chosen for server-focus kernels and distributions. But there are some things that need to be worked around.

Certain build processes determine the page size at compile time and assume it's the same at run time, and fail if it is not: https://github.com/jemalloc/jemalloc/issues/467

Some memory-mapped files formats have assumptions about page granularity: https://bugzilla.redhat.com/show_bug.cgi?id=1979804

The file format issue applies to ELF as well. Some people patch their toolchains (or use suitable linker options) to produce slightly smaller binaries that can only be loaded if the page size is 4K, even though the ABI is pretty clear in that you should link for compatibility with up to 64K pages.

ndesaulniers• 2 years ago

Ossification.

If the page size has been 4k for decades for most OS' and architectures, people get sloppy and hard code that literal value, rather than query for it.

PhilipRoman• 2 years ago

Replacing compile time constants with function calls will always bring some trouble, suddenly you need to rearrange your structures, optimizations get missed (in extreme cases you can accidentally introduce a DIV instruction), etc. So it is not surprising that code assumes 4k pages.

phh2• 2 years ago

Google/Android doesn't care much about backward compatibility and broke programs released on Pixel 3 in Pixel 7. (the interdiction of 32bit-only apps is 2019 on Play Store, Pixel 7 is first 64bits only device, while Google still released 32bits only device in 2023...). They quite regularly break apps in new Android versions (despite their infrastructure to handle backward compatibility), and app developers are used to brace themselves around Android & Pixel releases

reissbaker• 2 years ago

Generally I've found Google to care much more about not breaking old apps compared to Apple, which often expects developers to rebuild apps for OS updates or else the apps stop working entirely (or buy entirely new machines to get OS updates at all, e.g. the Intel/Apple Silicon transition). Google isn't on the level of Windows "we will watch for specific binaries and re-introduce bugs in the kernel specifically for those binaries that they depend on" in terms of backwards compatibility, but I wouldn't go so far as to say they don't care. I'm not sure whether that's better or worse: there's definitely merit to Apple's approach, since it keeps them able to iterate quickly on UX and performance by dropping support for the old stuff.

Veserv2• 2 years ago

Having both 4KB and 16KB simultaneously is either easy or hard depending on which hardware feature they are using for 16KB pages.

If they are using the configurable granule size, then that is a system-wide hardware configuration option. You literally can not map at smaller granularity while that bit is set.

You might be able to design a CPU that allows your idea of partial pages, but there be dragons.

If they are not configuring the granule size, instead opting for software enforcement in conjunction with always using the contiguous hint bit, then it might be possible.

However, I am pretty sure they are talking about hardware granule size, since the contiguous hint is most commonly used to support 16 contiguous entrys (though the CPU designer is technically allowed to do whatever grouping they want) which would be 64KB.

stingraycharles• 2 years ago

I’m a total idiot, how exactly is page size a CPU issue rather than a kernel issue? Is it about memory channel protocols / communication?

Disks have been slowly migrating away from the 4kb sector size, is this a same thing going on? That you need to actual drive to support it, because of internal structuring (i.e. how exactly the CPU aligns things in RAM), and on some super low level 4kb / 16kb being the smallest unit of memory you can allocate?

And does that then mean that there’s less overhead in all kinds of memory (pre)fetchers in the CPU, because more can be achieved in less clock cycles?

sweetjuly2• 2 years ago

Hmm, I'm not sure that's quite right. ARMv8 supports per TTBR translation granules [1] and so you can have 4K and 16K user processes coexisting under an arbitrary page size kernel by just context switching TCR.TG0 at the same time as TTBR0. There is no such thing as a global granule size.

[1] https://arm.jonpalmisc.com/2023_09_sysreg/AArch64-tcr_el2#fi...

lxgr3• 2 years ago

all old binaries break and emulators which emulate normal systems with 4KB pages

Would it actually affect the kind of emulators present on Android, i.e. largely software-only ones, as opposed to hardware virtualizers making use of a CPU's vTLB?

Wine is famously not an emulator and as such doesn't really exist/make sense on (non-x86) Android (as it would only be able to execute ARM binaries, not x86 ones).

For the downvote: Genuinely curious here on which type of emulator this could affect.

Zefiroj• 2 years ago

The support for mTHP exists in upstream Linux, but the swap story is not quite there yet. THP availability also needs work and there are a few competing directions.

Supporting multiple page sizes well transparently is non-trivial.

For a recent summary on one of the approaches, TAO (THP Allocation Optimization), see this lwn article: https://lwn.net/Articles/974636/

eyalitki• 2 years ago

RHEL tried that in that past with 64KB on AARCH64, it led to MANY bugs all across the software stack, and they eventually reverted it - https://news.ycombinator.com/item?id=27513209.

I'm impressed by the effort on Google's side, yet I'll be surprised if this effort will pay off.

nektro• 2 years ago

apple's m-series chips use a 16kb page size by default so the state of things has improved significantly with software wanting to support asahi and other related endeavors

kcb• 2 years ago

Nvidia is pushing 64KB pages on their Grace-Hopper system.

rincebrain2• 2 years ago

I didn't realize they had reverted it, I used to run RHEL builds on Pi systems to test for 64k page bugs because it's not like there's a POWER SBC I could buy for this.

daghamm2• 2 years ago

Can someone explain those numbers to me?

5-10% performance boost sounds huge. Wouldn't we have much larger TLBd if page walk was really this expensive?

On the other hand 9% increase in memory usage also sounds huge. How did this affect memory usage that much?

scottlamb• 2 years ago

5-10% performance boost sounds huge. Wouldn't we have much larger TLBd if page walk was really this expensive?

It's pretty typical for large programs to spend 15+% of their "CPU time" waiting for the TLB. [1] So larger pages really help, including changing the base 4 KiB -> 16 KiB (4x reduction in TLB pressure) and using 2 MiB huge pages (512x reduction where it works out).

I've also wondered why the TLB isn't larger.

On the other hand 9% increase in memory usage also sounds huge. How did this affect memory usage that much?

This is the granularity at which physical memory is assigned, and there are a lot of reasons most of a page might be wasted:

* The heap allocator will typically cram many things together in a page, but it might say only use a given page for allocations in a certain size range, so not all allocations will snuggle in next to each other.

* Program stacks each use at least one distinct page of physical RAM because they're placed in distinct virtual address ranges with guard pages between. So if you have 1,024 threads, they used at least 4 MiB of RAM with 4 KiB pages, 16 MiB of RAM with 16 KiB pages.

* Anything from the filesystem that is cached in RAM ends up in the page cache, and true to the name, it has page granularity. So caching a 1-byte file would take 4 KiB before, 16 KiB after.

[1] If you have an Intel CPU, toplev is particularly nice for pointing this kind of thing out. https://github.com/andikleen/pmu-tools

95014_refugee• 2 years ago

I've also wondered why the TLB isn't larger.

Fast CAMs are (relatively) expensive, is the excuse I always hear.

ein0p2• 2 years ago

No mention of Apple on the page. Apple has been using 16K pages for years now.

zahlman• 2 years ago

Why would an "Android news" blog mention what competitors are doing?

ein0p2• 2 years ago

Because the whole thing sounds like they’re doing something new, but they’re just catching up to something Apple has done back when they switched to aarch64.

dboreham• 2 years ago

Time to grab some THP popcorn...

taeric2• 2 years ago

I see they have measured improvements in the performance of some things. In particular, the camera app starts faster. Small percentage, but still real.

Curious if there are any other changes you could do based on some of those learnings? The camera app, in particular, seems like a good one to optimize to start instantly. Especially so with the the shortcut "double power key" that many phones/people have setup.

Specifically, I would expect you should be able to do something like the lisp norm of "dump image?" Startup should then largely be loading the image, not executing much if any initialization code? (Honestly, I mostly assume this already happens?)

saagarjha8• 2 years ago

A big part of the challenge for launching the camera app is getting the hardware ready and quickly freeing up RAM for image processing.

taeric2• 2 years ago

Makes sense. That it is so much faster on repeat wakeups does seem to hint that it could be computing a something. I'm assuming you are saying that most of what is getting computed is related to paging in/out memory? That would track on how it could be better with larger pages.

quotemstr4• 2 years ago

Good. It's about time. 4KB pages come down to us from 32-bit time immemorial. We didn't bump the page size when we doubled the sizes of pointers and longs for the 64-bit transition. 4KB has been way too small for ages, and I'm glad we're biting the minor compatibility bullet and adopting a page size more suited to modern computing.

jeffbee• 2 years ago

Now do 512B LBAs on NVMe devices.

lxgr3• 2 years ago

Now I wonder: Does increased page size have any negative impacts on I/O performance or flash lifetime, e.g. for writebacks of dirty pages of memory-mapped files where only a small part was changed?

Or is the write granularity of modern managed flash devices (such as eMMCs as used in Android smartphones) much larger than either 4 or 16 kB anyway?

tadfisher• 2 years ago

Flash controllers expose blocks of 512B or 4096KB, but the actual NAND chips operate in terms of "erase blocks" which range from 1MB to 8MB (or really anything); in these blocks, an individual bit can be flipped from "0" to "1" once, and flipping any bit back to "0" requires erasing the entire block and flipping the desired bits back to "1" [0].

All of this is hidden from the host by the NAND controller, and SSDs employ many strategies (including DRAM caching, heterogeneous NAND dies, wear-leveling and garbage-collection algorithms) to avoid wearing the storage NAND. Effectively you must treat flash storage devices as block devices of their advertised block size because you have no idea where your data ends up physically on the device, so any host-side algorithm is fairly worthless.

[0] https://spdk.io/doc/ssd_internals.html

lxgr3• 2 years ago

Writes on NAND happen at the block, not the page level, though. I believe the ratio between the two is usually something like 1:8 or so.

Even blocks might still be larger than 4KB, but if they’re not, presumably a NAND controller could allow such smaller writes to avoid write amplification?

The mapping between physical and logical block address is complex anyway because of wear leveling and bad block management, so I don’t think there’s a need for write granularity to be the erase block/page or even write block size.

CalChris4• 2 years ago

  iOS has had 16K pages since forever.
  OSX switched to 16K pages in 2020 with the M1.
  Windows is stuck on 4K pages, even for AArch64.
  Linux has various page sizes. Asahi is 16K.

nullindividual7• 2 years ago

Windows has 4K, 2M, and 1G page sizes on x86-64.

CalChris4• 2 years ago

Normal, large and huge. But default normal pages (which is what Android is changing) are 4K. FWIW, Itanium and Alpha had 8K default pages.

https://devblogs.microsoft.com/oldnewthing/20210510-00/?p=10...

I wonder why Microsoft stayed with 4K for AArch64.

baby_souffle• 2 years ago

and 1G page sizes on x86-64.

I wonder who requested the 1G page size be implemented and what they use it for...

iam-TJ• 2 years ago

In Debian kernel we've very recently enabled building an ARM64 kernel flavour with 16KiB page size and we've discussed adding a 64KiB flavour at some point as is the case for PowerPC64 already.

This will likely reveal bugs that need fixing in some of the 70,000+ packages in the Debian archive.

That ARM64 16KiB page size is interesting in respect of the Apple M1 where Asahi [0] identified that the DART IOMMU has a minimum page size of 16KiB so using that page size as a minimum for everything is going to be more efficient.

[0] https://asahilinux.org/2021/10/progress-report-september-202...

pflanze• 2 years ago

I would expect that this increases the gap between new and old phones / makes old phones unusable more quickly: new phones will typically have enough RAM and can live with the 9% less efficient memory use, and will see the 5-10% speedup. Old phones are typically bottlenecked at RAM, now 9% earlier, and reloading pages from disk (or swapping if enabled) will have a much higher overhead than 5-10%.

Adding 16 kb page size to Android

Related Stories