未加星标

Write your own kmalloc

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二05 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏

While at Linaro connect, I was discussing with someone the state of the Energy Aware Scheduler (EAS) patches. This is an ongoing project to update the linux kernel scheduler to be aware of processor hardware to make better scheduling decisions and reduce power usage. Parts of the patch set have been accepted upstream but a large part still exists out of tree. The patch set is fairly intrusive and the scheduler in the kernel is a finicky piece of code. The EAS patches take a good bit work to maintain which brought up a general discussion of what subsystems would be easier or harder to replace than the scheduler. Someone proposed that kmalloc would be difficult but thinking about it, kmalloc is one of the easier places to write a new implementation.

kmalloc in the kernel serves the same purpose as malloc in userspace; it allocates heap memory. The fundamental behavior works the same as in userspace too:

malloc(something) try to allocate some memory if (I found some memory) return what I found else increase my heap if (I can't increase my heap) uh oh out of memory :( try to allocate some memory if (I found some memory) return what I found else uh oh out of memory :(

Yes, this is very hand wavy. The point here is that the heap is dynamic, it grows with the size of the program. In userspace, the size of the heap is controlled by sbrk or a similar system call. In the kernel, kmalloc makes calls to the underlying page allocator ( alloc_page ). This is a part of the kernel that many people get confused about, what's the difference between a call to kmalloc and a call to alloc_pages ? alloc_pages is the lowest level memory allocator using buddy allocation to allocate pages in PAGE_SIZE order. A typical page size is 4096 bytes. Most allocations do not require 4096 bytes. kmalloc sits on top of the buddy allocator to manage smaller allocation sizes. In general, the buddy allocator is only used directly when a physically contiguous PAGE_SIZE allocation is needed. kmalloc should be used unless there is a specific use case in mind.

The slab allocator works on top of alloc_pages . The kernel currently offers three different algorithms, SLOB, SLAB, and SLUB. There was a very good talk a few years ago about the differences between these allocators. In general, SLOB is old and isn't used except in select circumstances, SLAB was the replacement followed by SLUB. Most of the work these days is done on SLUB. The different allocators are kept around because some people care about the use cases where one performs better than another. Because of this, the code is written to make it easy to add a drop in replacement.

I decided to see just how self-contained a new allocator would be.

I started by defining a new Kconfig item in init/Kconfig to select a new algorithm type.

Defines for KMALLOC_MIN_SIZE , KMALLOC_SHIFT_LOW , KMALLOC_SHIFT_HIGH were needed. I borrowed the definitions from SLAB for the purposes of compiling.

struct kmem_cache had to be defined in mm/slab.h I ended up just using the same definition as CONFIG_SLOB plus a node field for some #ifndef CONFIG_SLOB

At this point, the kernel would compile but fail to link. I added stub functions for kfree , __kmalloc , kmem_cache_alloc , kmem_cache_free , __kmalloc_node , kmem_cache_alloc_trace , kmem_cache_alloc_node_trace , kmem_cache_alloc_node , kmem_cache_free_bulk , kmem_cache_alloc_bulk , ksize , __kmalloc_node_track_caller , __kmalloc_track_caller , kmem_cache_init , kmem_cache_init_late , __kmem_cache_shutdown , __kmem_cache_release , __kmem_cache_shrink , __kmem_cache_alias , __kmem_cache_create , kmem_cache_flags , a total of 21 functions.

And that was enough to get the kernel to compile. Obviously this kernel won't boot since the stub malloc always returns NULL .

Compared to replacing other fundamental parts of the kernel, this was very easy. The code changes needed outside a file that contained a new implementation (or in my case stubs) were fairly small. Does this mean everyone should go out and write a brand new allocator for submission to the community? Almost certainly not. Most work upstream should be on expanding existing allocators. A new allocator would need piles of benchmarking and research to be considered for acceptance, and it would have to be better than what's there. It's much better to have one allocator that works for as many cases as possible versus a new allocator for every use case. That doesn't mean research shouldn't happen on your own. Writing your own memory allocator is an excellent project for learning that doesn't need to be submitted to the community. If you've never written an allocator before (in user or kernel space) I highly recommend it. Forking off one of the existing allocators and making changes on top can be a great way to compare against a known baseline. Once your changes are validated, they can be submitted to the existing allocator.

In conclusion, kmalloc in the kernel is self contained, sobreak your kernel by experimenting with it. You might get some ideas that can be turned into a project for existing allocators.

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: LinuxUBSLUHIG
分页:12
转载请注明
本文标题:Write your own kmalloc
本站链接:http://www.codesec.net/view/481621.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(29)