Trường Đại Học Bách Khoa Hà Nội
Viện Điện Tử Viễn Thông
====o0o====
BÁO CÁO BÀI TẬP DÀI MÔN HỆ
ĐIỀU HÀNH
Bài tập số 2:
Chương trình sửa mã nguồn hệ điều hành Linux báo cáo dung lượng
Ram và thu hồi bộ nhớ theo cơ chế slab cache
Giáo viên hướng dẫn : PHẠM VĂN TIẾN
Sinh viên thực hiện : Lương Kim Doanh
Ngô Quang Thìn
Trần Hoàng Điệp
Nguyễn Trung Thành
Lớp : KSTN-ĐTVT-K52
HÀ NỘI 10/2011
1

Mục Lục:





 !!"!
#$%%&!
'%(!
)"*#)+!
#!%,%#)+-
#.%./012#)+-
3")"*#)+-

thời gian để quản lí bộ nhớ sẵn có. Chùng ta cũng có thể phát triển một thuật toán mà
quản lí bộ nhớ một cách hiệu quả về thời gian nhưng sẽ tốn nhiều tài nguyên hệ thống
hơn. Kết cục một ứng dụng cụ thể chỉ ưu tiên chọn một trong hai xu hướng phú hợp nhất.
Việc quản lí bộ nhớ trước đây dựa vào chiến lược cấp phát dựa vào heap. Trong
phương thức này một khối bộ nhớ lớn (người ta gọi la heap) được sử dụng để cấp bộ nhớ
cho mục đích của người sử dụng. Khi người sử dụng cần một khối bộ nhớ, họ yêu cầu
heap manager tìm kiếm lượng bộ nhớ thoả mãn và trả về khối tìm được. Một vài thuật
toán được sử dụng để tìm kiếm là first-fit (khối đấu tiên tìm được trong heap thỏa mãn
yêu cầu). Khi người sử dụng hoàn tất công việc, khối bộ nhớ đươc trả lại cho heap.
Vấn đề chủ yếu phát sinh với chiến lược cấp phát dựa vào heap này là sự phân
mảnh (fragmentation). Khi khối bộ nhớ được cấp phát, chúng sau đó được trả lại theo thứ
tự khác nhau vào những thời điểm khác nhau. Điều này dẫn đến việc để lại những chỗ
trống trong heap, yêu cầu nhiếu thời gian hơn để quản lí bộ nhớ rỗi. Thuật toán này
hường đến việc quản lí tài nguyên bộ nhớ một cách hiệu quả nhưng yêu cầu thời gian để
quản lí heap.
Một phương pháp khác là cấp phát bộ nhớ theo kiểu bè bạn (buddy memory
allocation), là kĩ thuất cấp phát nhanh hơn mà chia bộ nhó thành các phân vùng
(partition) mũ cơ số 2 và thử cấp phát bộ nhớ yêu cấu sử dụng phương pháp best-fit. Khi
bộ nhớ cấp phát cho ngưới sử dụng được giải phóng, khối buddy được kiểm tra để xem
3

liệu bất kì hàng xóm nào của nó đang rỗi hay không. Nếu có, những khối nhớ này được
hợp lại để giảm những lãng phí bộ nhớ do phương pháp best-fit.
2. Giới thiệu slab cache
Bộ cấp phát slab được sử dụng trong Linux dựa vào thuật toán được giới thiệu bởi
Jeff Bonwick cho hệ điều hành SunOS. Giải pháp cấp phát của Jeff Bonwick xoay quanh
việc đệm đối tượng (object caching). Bên trong kernel, một lượng đáng kể bộ nhớ được
cấp phát cho một tập hữu hạn các đối tượng như miêu tả tập tin ( file descriptor) và các
cấu trúc thông dụng khác. Jeff nhận thấy rằng thời gian cần thiết để khởi tạo một object
thông thường trong kernel vượt quá thời gian cần thiết để cấp phát và giải phóng nó. Jeff

dụng
objsize: kích thước của object trong cache
active_slabs : số lượng slab đang được sử dụng của cache
num_clabs: số lượng slab cấp phát cho cache.
Nếu SMP được enable thì thêm 2 trường nữa được thêm vào:
- limit: Số lượng free object mà pool (object pools) có thể có trước khi một nửa được trả lại cho
global pool
- batchcount: là số lượng object được cấp phát cho CPU khi không có object free.
6

Để tăng tốc cấp phát và giải phóng object và slab , chúng được chia a thành ba danh
sách : slabs_full, slabs_partial và slab_free. Tất cả các object trong slabs_full đã được sử dụng,
slabs_partial có object, vì vậy được dung chủ yếu cho việc cấp phát đối tượng, slabs_free không
có đối tượng nào được cấp phát, vì vậy được dung chủ yếu cho việc hủy slab.
1.1.Cache Descriptor:
Tất cả thông tin về 1 cache được lưu trong cấu trúc kmem_cache được khai báo trong
Include/linux/slub_def.h (nếu kernel sử dụng SLUB thì cấu trúc này nằm trong file
include/linux/slub_def.h)
1.2.Những cờ static của cache:
SLUB_HWCACHE_ALIGN: đặt object vào L1 CPU cache
SLUB_CACHE_DMA: cấp phát slab từ vùng nhớ ZONE_DMA
Nếu tùy chọn CÒNIG_SLAB_DEBUG được set sẽ có thêm 1 số tùy chọn:
SLAB_DEBUG_FREE: khi thi hành việc kiểm tra object free.
SLAB_RED_ZONE: đánh dấu object đầu và object cuối và bẫy tràn
SLAB_POISON : “nhiễm độc” object làm cho nó không được cấp phát hay khởi tạo
Để ngăn việc sử dụng sai các cờ, một CREATE_MASK được tạo ra trong mm/slab.c
chứa tất cả các cở được cho phép. Khi một cache được tạo ra, các cờ yêu cầu được so sánh với
CREATE_MASK và được coi như là một lỗi nếu sử dụng sai cờ
1.3. Cache coloring:
Để sử dụng hardware cache tốt hơn, slab allocator sẽ dịch (offset) object trong các slab


Khi một slab được giải phóng, nó được đặt vào danh sách slabs_free cho sự sử dụng sau
này. Cache không tự động shrink, vì vậy khi swap chú ý rằng bộ nhớ khan hiếm, nó gọi
kmem_cache_reap() để giải phóng không gian nhớ. Hàm này chịu trách nhiệm tìm kiếm một
cache mà sẽ được yêu cầu shrink bộ nhớ nó sử dụng. Cache reaping không tính đến việc node
hay vùng nào đang yêu cầu cấp phát (pressure). Điều này có nghĩa là, với một cấu trúc NUMA
hay HIGH MEMORY, có khả năng kenel dành rất nhiều thời gian giải phóng bộ nhớ từ vùng
không gian yêu cầu cấp phát, nhưng vấn đề này không xảy ra với những kiến trúc như x86, kiến
trúc mà chỉ có một bank memory.
1.6. Cache shrinking :
Khi một cache được chọn để shrink chính nó, những bước sau được thực hiện :
.delete hết tất cả các object trong mỗi CPU cache
. delete tất cả các slab từ slabs_free nếu cờ grow không được set
9Kmem_cache_shrink() xóa tất cả các slab từ slabs_free và trả lại số page được giải phóng , hàm
cơ sở này được export cho những người sử dụng slab allocator.
10

Hàm thứ hai,_kmem_cache_shrink() giải phóng tất cả các slab từ slabs_free và sau đó
kiểm tra lại xem slabs_partial và slabs_full có rỗng khống. Hàm này chỉ được sử dụng bên trong
module và rất quan trọng khi hủy cache, nó không quan tâm số page được giải phóng chỉ miễn là
cache rỗng.
1.7. Cache Destroying:
Khi 1 mode unload, nó có trách nhiệm phải xóa bỏ bất kì cache nào với hàm
kmem_cache_destroy(). Mã nhân kennel không chủ động destroy cache của nó bởi vì sự tồn tại
của chúng là cần thiết cho hệ thống. Những bước được thực hiện để xóa bỏ cache:
. Delete cache từ cache chain
. Shrink cache để delete tất cả các slab

{1024, NULL, NULL},
{2048, NULL, NULL},
{4096, NULL, NULL},
{8192, NULL, NULL},
{16384, NULL, NULL},
{32768, NULL, NULL},
{65536, NULL, NULL},
{131072, NULL, NULL},
{0, NULL, NULL},
Hiển nhiên, dãy kích cỡ tĩnh này chứa các bộ đệm từ 2
5
đến 2
17
, dãy này được khởi tạo
vào thời điểm bắt đầu chạy hệ thống
2. Slab:
Cấu trúc quản lý slab:
Struct slab {
12

truct list_head list;
unsigned long colouroff;
void *s_mem; /* bao gồm colour offset*/
unsigned int inuse; /* số lượng object đang được sử dụng trong slab */
kmem_bufctl_t free
unsigned short nodeid;}
list : đây là danh sách liên kết của slab (slabs_free, slabs_partial, slabs_full)
colouroff: độ dịch từ địa chỉ cơ sở của object đầu tiên trong slab
free: đây là 1 dãy bufctl được sử dụng để lưu vị trí của free object


typedef unsigned int kmem_bufctl_t;
Bởi vì dãy này đứng sau slab descriptor và không có con trỏ trực tiếp đến phần tử đầu tiên một
cách trực tiếp, một macro trợ giúp được khai báo
static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
{
return (kmem_bufctl_t*)(slabp+1);
}
Khi cấp phát một object, kmem_cache_alloc() thực hiện công việc câp nhật dãy
kmem_bufctl (). Trường slab free giữ chỉ số của free object đầu tiên, chỉ số free object tiếp
theo là kmem_bufctl_t [slabfree] diễn giải như sau:
objp= slabp->_mem+ slabp->free*cachep-> objsize;
slabp->free= slab_bufctl (slabp) [slabp-> free];
2.4 Tính toán số object trong 1 Slab:
Trong quá trình tạo cache, hàm cache_ estimate() được gọi để tính xem có bao nhiêu
object được lưu trên 1 slab, tính trong 2 trường hợp slab descriptor được lưu trong hay ngoài slab
và kích cỡ của kmem_bufctl_t cần được track nếu 1 object là rỗi hay không. Nó trả lại số object
có thể chứa được và số byte lãng phí. Số byte lãng phí có ý nghĩa quan trọng nếu cache coloring
được sử dụng. Tính toán này được thực hiện theo những bước sau:
.Khởi tạo số byte lãng phí bằng tổng kích cỡ slab, nghĩa là PAGE_SIZE
gfporder
. Trừ đi lượng không gian yêu cầu để lưu slab descriptor.
.Đếm số lượng object có thể được lưu bao gồm kích thước của kmem_bufctl_t nếu slab
descriptor được lưu ở trong slab. Tiếp tục tăng kích cỡ cho tới khi slab được điền đầy
. Trả lại số object và số byte lãng phí
2.5 Slab Destroying:
16

Khi một cache bị shring hay destroy, slab bị delete. Bởi vị object có thể có hàm hủy
(destructor) hàm này phải được gọi. Các công việc để delete một slab như sau:
. Nếu có thể, gọi hàm destructor cho mọi object trong slab

CPU lâu nhất có thể. Linux thưc hiên điều này bằng cách cố gắng giữ object trong cùng một
CPU cache với per-CPU object cache, đơn giản được gọi là cpu cache cho mỗi cpu trên hệ
thống. Khi cấp phát hay giải phóng object, chúng được đặt ở cpu cache. Khi không có object nào
được giải phóng, một nhóm object được đặt vào trong pool. Khi pool trở nên quá lớn, một nửa bị
loại và đặt vào global cache. Với cách này, cache cứng trên cùng một CPU sẽ được sử dụng lâu
nhất có thể. Lợi ích thứ hai cưa phương pháp này là không phải sử dụng spinlock khi CPU truy
cập pool bởi vì CPU sẽ không thể truy cập được dữ liệu cục bộ khi object đã được gán cho CPU
này.
18

4.1. Cho phép CPU cache:
Khi một cache được tạo ra, CPU cache của nó phải được kích hoạt và bộ nhớ được cấp
phát cho nó sử dụng kmalloc(). Hàm enable_cpucache() có trách nhiệm cho việc quyết định kích
cỡ cache và gọi hàm do_tune_cpucache() để cấp phát bộ nhớ cho nó.
Tất nhiên, một CPU cache không thể tồn tại cho đến khi một size cache được chỉ định, vì
vậy biến toàn cục g_cpu_cache_up được sử dụng để gắn CPU cache được cho phép quá sớm.
Sau khi CPU cache đươc thiết lập, nó có thể được truy cập mà không phải lock vì một CPU
không bao giờ truy cập sai cpucache
4.2. Cập nhật thông tin mỗi CPU:
Khi cache mối CPU được tạo ra hay thay đổi, mỗi CPU đươc thông báo bởi một IPI. Nớ
sẽ không thể thay đổi tất cả giá trị trong cache descriptor bởi vì điều này dẫn đến vấn đề nhất
quán cache và phải dùng spinlock để bảo vệ CPU cache. Thay vào đó một cấu trúc
ccupdate_struct được định nghĩa với tất cả thông tin mà mỗi CPU cần, và mỗi CPU swap dữ liệu
mới với thông tin cũ trong cache descriptor. Cấu trúc được định nghĩa như sau:
Struct ccupdate_struct
{
Struct kmem_cache *cachep;
Struc aray_cache *new[NR_CPUS];
};
Cachep là cache được update và new là dãy các CPU descriptor cho mỗi CPU trên hệ

đươc giải phóng trước khi gọi free_pages ().
III. Triển khai.
1. Giới thiệu thư mục/proc/sys.
Nhứng file mà người sử dụng quan sát thấy ở thư mục này thực chất là những biến
kernel. Với mỗi biến, kernel có thể định nghĩa:
• Nơi đặt của nó trong / proc/ sys. Những biến liên quan đến cùng thành phần và thuộc tính
của kernel thường được đặt chung trong một thư mục.
Ví dụ, trong / proc/ sys/ net/ ipv4, ta có thể tìm thấy những file liên quan đến Ipv4.
20

• Tên của nó. Phần lớn, các file được đặt tên đơn giản giống với tên biến của kernel, nhưng
thỉnh thoảng tên của chúng được thay đổi một chút cho thân thiện hơn.
• Quyền truy cập flie. Ví dụ, 1 file có thể cho mọi người đều đọc được nhưng chỉ cho root
có quyền thay đổi.
Nội dung của những biến được xuất ra / proc/ sys có thể đọc hoặc ghi bằng cách truy cập
các file liên quan (khi ta có được cấp quyền) và trực tiếp gọi đến system call sysctl.
Những thư mục và file được xác định vào lúc khởi động, một vài file khác được thêm vào
lúc chạy. Những sự kiện dẫn đến sự tạo ra file và thư mục lúc chạy là:
- Khi module kernel thực thi 1 tính năng mới hoặc 1 module được load hay unload.
- Khi 1 device driver được đăng kí (register) hoặc bị loại bỏ (unregister). Có những tham
số cấu hình mà chỉ có 1 thể hiện mỗi device. Ví dụ, /proc/ sys/ net/ipv4/ neigh có một thư mục
con cho mỗi network device.
Cả file và thư mục trong / proc/ sys được định nghĩa với cấu trúcctl_table. Cấu trúc này
được đăng kí và bị xóa (register và unregister) với hàm register_sysctl_table và
unregister_sysctl_table, được dịnh nghĩa trong kernel/ sysctl.c.
Cá trường quan trọng của ctl_data:
Const char *procname
Tên file được sử dụng trong/ proc/ sys
int maxlen
Kích cỡ của biến kernel được export.

Mặc dù mang tính chất “monolithic” (nguyên khôi) khi toàn bộ kernel chạy trong một
protecion domain (miền bảo vệ) đơn nhưng linux kernel có tính chất module. Điều này cho
người lập trình có thể thêm vào hay bớt đi code từ kerel một cách linh động và ngay cả khi
kernel vẫn đang chạy. Các chương trình con, dữ liệu và thực thể liên quan cùng với các điểm tồn
tại được nhóm lại với nhau trong một ảnh nhị phân đơn lẻ, một thực thể kernel có khả năng nạp
được vào hệ thống thì được gọi là Module.
Việc hộ trợ khả năng sử dụng modules khiến hệ thống chỉ cần có tối thiểu một ảnh kernel
cơ bản với những tính chất và driver tùy chọn. Với điểm dễ dàng thêm và bớt khỏi mã kernel nên
midule làm tăng khả năng debug (gỡ rối) cho hệ thống , đồng thời cho phép nạp thêm vào những
drive mới để hệ thống đáp ứng được đòi hỏi cắm nóng thiết bị (hot plugging).
22

2.1 Xây dựng Module
Từ Version 2.6 trở đi, việc xây dựng module đã trở nên dễ dàng hơn, nhờ có hệ thống
“kbuild”.Điều đầu tiên khi xây dựng một module là quyết định xem mã nguồn của module sẽ
chạy ở đâu. Bạn có thể thêm module vào kernel hợp lý dưới dạng patch hoặc bằng cách đưa code
của bạn vào cây chính (official tree). Ngoài ra, bạn cũng có thể xây dựng và duy trì module bên
ngoài cây nguồn (source tree).
At home in the source tree
Khi xây dựng module, nếu bạn có thể đưa module của bạn vào như một phần chính thức
của Linux và nó tồn tại trong cây nguồn kernel thì đó là một cách làm lý tưởng, việc này đòi hỏi
một số thao tác chuẩn bị ban đầu nhưng nó vẫn thường là phương pháp hay được dùng.
Bước đầu tiên là việc quyết định xem bạn sẽ để module của mình nằm ở đâu trong cây
nguồn kernle. Bên trong thư mục này, chúng được chia ra hơn nữa dựa trên lớp, kiểu và thậm chí
là theo từng drive cụ thể. Các thiết bị hướng kí hiệu được đặt trong thư mục drives/char trong
thiết bị hướng block được đặt trong drivers/block, thiết bị USB được đặt trong thư mục:
drive/usb/. Những nguyên tắc đặt vị trí này không quá cứng nhắc bởi vì nhiều thiết bị USB cũng
đồng thời là thiết bị hướng kí hiệu, nhưng cuối cùng, thì việc tổ chức thư mục này cũng tương
đối dễ hiểu và chính xác.
Giả sử rằng bạn có một thiết bị hướng kí hiệu và muốn đặt nó vào trong thư mục

cùng, bạn cần đặt các cờ biên dịch gcc trong quá trình xây dựng file của bạn, cụ thể, them dòng
sau vào trong Makefile:
EXTRA_CFCLASS += - DTITANIUM_POLE
Nếu bạn chọn đặt file nguồn của mình vào trong drivers/char/ và không tạo ra thư mục
mới, hầu như bạn chỉ cần đặt các dòng phía trên (mà bạn đặt trong Makefile trong thư mục
drivers/char/fishing/) vào trong thư mục driver/ char/ Makefile.
Để biên dịch, chạy quá trình buil của kernel như thường lệ, nếu như việc dựng module của bạn là
có điều kiện với một tùy chọn cấu hình, như đã cấu hình trong thông số
CONFIG_FISHING_POLE, đảm bảo rằng các tùy chọn này được kích họat trước khi bắt đầu
quá trình tạo module.
Living Externally
Nếu bạn mong muốn xây dựng và duy trì module của mình bên ngòai cây nguồn kernel,
để hoạt động như một thành phần bên ngòai, bạn cần tạo một Makefile trong thư mục mã nguồn
của riêng bạn với một dòng như sau:
Obj-m: fishing.o
Fishing-obs: =fishing-main.o fishing-line.o
24

Thao tác này sẽ được biên dịch file fishing –main.c và fishing-line.c thanh fishing.ko
Sự khác biệt cơ bản của phương pháp này nằm ở quá trình xây dựng (build), bởi vì
module được tạo ra sẽ nằm ngòai cây kernel nên bạn cần chỉ cho lệnh make tìm đến các file
nguồn của kernel và Makefile, để làm được điều này, bạn sử dụng lênh sau:
Make –c/kernel/source/location SUBDIRS=$PWD module
Trong đó, kernel/source/location là cây nguồn kernel đã được cấu hình của bạn.
Chú ý rằng, bạn không được đặt một bản copy của cây nguồn kernel đang chạy vào trong thư
mục /usr/src/linux mà phải đặt vào một nơi nào khác, dễ dàng truy cập đến, ví dụ như thư mục
nhà của bạn (home directory)
2.2 Exported Symbols
Khi modules được load, chúng sẽ liên kết động đến nhâ. Với không gian người dung, mã
nhị phân được liên kết động chỉ có thể gọi đến hàm chức năng bên ngoài mà đã được xuất ra một