TheSlabAllocatorAnObject-CachingKernelMemoryAllocator

Linux

slab

需积分: 16 123 浏览量更新于2023-05-27 评论收藏 54KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

The Slab Allocator:

An Object-Caching Kernel Memory Allocator

Jeff Bonwick

Sun Microsystems

Abstract

This paper presents a comprehensive design over-

view of the SunOS 5.4 kernel memory allocator.

This allocator is based on a set of object-caching

primitives that reduce the cost of allocating complex

objects by retaining their state between uses. These

same primitives prove equally effective for manag-

ing stateless memory (e.g. data pages and temporary

buffers) because they are space-efﬁcient and fast.

The allocator’s object caches respond dynamically

to global memory pressure, and employ an object-

coloring scheme that improves the system’s overall

cache utilization and bus balance. The allocator

also has several statistical and debugging features

that can detect a wide range of problems throughout

the system.

1. Introduction

The allocation and freeing of objects are among the

most common operations in the kernel. A fast ker-

nel memory allocator is therefore essential. How-

ever, in many cases the cost of initializing and

destroying the object exceeds the cost of allocating

and freeing memory for it. Thus, while improve-

ments in the allocator are beneﬁcial, even greater

gains can be achieved by caching frequently used

objects so that their basic structure is preserved

between uses.

The paper begins with a discussion of object

caching, since the interface that this requires will

shape the rest of the allocator. The next section

then describes the implementation in detail. Section

4 describes the effect of buffer address distribution

on the system’s overall cache utilization and bus

balance, and shows how a simple coloring scheme

can improve both. Section 5 compares the

allocator’s performance to several other well-known

kernel memory allocators and ﬁnds that it is

generally superior in both space and time. Finally,

Section 6 describes the allocator’s debugging

features, which can detect a wide variety of prob-

lems throughout the system.

2. Object Caching

Object caching is a technique for dealing with

objects that are frequently allocated and freed. The

idea is to preserve the invariant portion of an

object’s initial state — its constructed state —

between uses, so it does not have to be destroyed

and recreated every time the object is used. For

example, an object containing a mutex only needs

to have mutex_init() applied once — the ﬁrst

time the object is allocated. The object can then be

freed and reallocated many times without incurring

the expense of mutex_destroy() and

mutex_init() each time. An object’s embedded

locks, condition variables, reference counts, lists of

other objects, and read-only data all generally qual-

ify as constructed state.

Caching is important because the cost of con-

structing an object can be signiﬁcantly higher than

the cost of allocating memory for it. For example,

on a SPARCstation-2 running a SunOS 5.4 develop-

ment kernel, the allocator presented here reduced

the cost of allocating and freeing a stream head

from 33 microseconds to 5.7 microseconds. As the

table below illustrates, most of the savings was due

to object caching:

_ ___________________________________________

Stream Head Allocation + Free Costs (µsec)

_ ___________________________________________

construction memory other

allocator + destruction allocation init.

_ ___________________________________________

old 23.6 9.4 1.9

new 0.0 3.8 1.9

_ ___________________________________________



Caching is particularly beneﬁcial in a mul-

tithreaded environment, where many of the most

frequently allocated objects contain one or more

embedded locks, condition variables, and other con-

structible state.

The design of an object cache is

straightforward:

To allocate an object:

if (there’s an object in the cache)

take it (no construction required);

else {

allocate memory;

construct the object;

}

To free an object:

return it to the cache (no destruction required);

To reclaim memory from the cache:

take some objects from the cache;

destroy the objects;

free the underlying memory;

An object’s constructed state must be initial-

ized only once — when the object is ﬁrst brought

into the cache. Once the cache is populated, allo-

cating and freeing objects are fast, trivial operations.

2.1. An Example

Consider the following data structure:

struct foo {

kmutex_t foo_lock;

kcondvar_t foo_cv;

struct bar *foo_barlist;

int foo_refcnt;

};

Assume that a foo structure cannot be freed until

there are no outstanding references to it

(foo_refcnt == 0) and all of its pending bar

events (whatever they are) have completed

(foo_barlist == NULL). The life cycle of a

dynamically allocated foo would be something like

this:

foo = kmem_alloc(sizeof (struct foo),

KM_SLEEP);

mutex_init(&foo->foo_lock, ...);

cv_init(&foo->foo_cv, ...);

foo->foo_refcnt = 0;

foo->foo_barlist = NULL;

use foo;

ASSERT(foo->foo_barlist == NULL);

ASSERT(foo->foo_refcnt == 0);

cv_destroy(&foo->foo_cv);

mutex_destroy(&foo->foo_lock);

kmem_free(foo);

Notice that between each use of a foo object we

perform a sequence of operations that constitutes

nothing more than a very expensive no-op. All of

this overhead (i.e., everything other than ‘‘use foo’’

above) can be eliminated by object caching.

2.2. The Case for Object Caching in the

Central Allocator

Of course, object caching can be implemented

without any help from the central allocator — any

subsystem can have a private implementation of the

algorithm described above. However, there are

several disadvantages to this approach:

(1) There is a natural tension between an object

cache, which wants to keep memory, and the

rest of the system, which wants that memory

back. Privately-managed caches cannot handle

this tension sensibly. They have limited

insight into the system’s overall memory needs

and no insight into each other’s needs. Simi-

larly, the rest of the system has no knowledge

of the existence of these caches and hence has

no way to ‘‘pull’’ memory from them.

(2) Since private caches bypass the central alloca-

tor, they also bypass any accounting mechan-

isms and debugging features that allocator may

possess. This makes the operating system

more difﬁcult to monitor and debug.

(3) Having many instances of the same solution to

a common problem increases kernel code size

and maintenance costs.

Object caching requires a greater degree of coopera-

tion between the allocator and its clients than the

standard kmem_alloc(9F)/kmem_free(9F)

interface allows. The next section develops an

interface to support constructed object caching in

the central allocator.

2.3. Object Cache Interface

The interface presented here follows from two

observations:

(A) Descriptions of objects (name, size, alignment,

constructor, and destructor) belong in the

clients — not in the central allocator. The

allocator should not just ‘‘know’’ that

sizeof (struct inode) is a useful pool

size, for example. Such assumptions are brittle

[Grunwald93A] and cannot anticipate the needs

of third-party device drivers, streams modules

and ﬁle systems.

(B) Memory management policies belong in the

central allocator — not in its clients. The

clients just want to allocate and free objects

quickly. They shouldn’t have to worry about

how to manage the underlying memory

efﬁciently.

It follows from (A) that object cache creation must

be client-driven and must include a full speciﬁcation

of the objects:

(1) struct kmem_cache *kmem_cache_create(

char *name,

size_t size,

int align,

void (*constructor)(void *, size_t),

void (*destructor)(void *, size_t));

Creates a cache of objects, each of size size,

aligned on an align boundary. The align-

ment will always be rounded up to the

minimum allowable value, so align can be

zero whenever no special alignment is required.

name identiﬁes the cache for statistics and

debugging. constructor is a function that

constructs (that is, performs the one-time ini-

tialization of) objects in the cache; destruc-

tor undoes this, if applicable. The construc-

tor and destructor take a size argument so

that they can support families of similar

caches, e.g. streams messages.

kmem_cache_create returns an opaque

descriptor for accessing the cache.

Next, it follows from (B) that clients should need

just two simple functions to allocate and free

objects:

(2) void *kmem_cache_alloc(

struct kmem_cache *cp,

int flags);

Gets an object from the cache. The object will

be in its constructed state. flags is either

KM_SLEEP or KM_NOSLEEP, indicating

whether it’s acceptable to wait for memory if

none is currently available.

(3) void kmem_cache_free(

struct kmem_cache *cp,

void *buf);

Returns an object to the cache. The object

must still be in its constructed state.

Finally, if a cache is no longer needed the client can

destroy it:

(4) void kmem_cache_destroy(

struct kmem_cache *cp);

Destroys the cache and reclaims all associated

resources. All allocated objects must have

been returned to the cache.

This interface allows us to build a ﬂexible allocator

that is ideally suited to the needs of its clients. In

this sense it is a ‘‘custom’’ allocator. However, it

does not have to be built with compile-time

knowledge of its clients as most custom allocators

do [Bozman84A, Grunwald93A, Margolin71], nor

does it have to keep guessing as in the adaptive-ﬁt

methods [Bozman84B, Leverett82, Oldehoeft85].

Rather, the object-cache interface allows clients to

specify the allocation services they need on the ﬂy.

2.4. An Example

This example demonstrates the use of object cach-

ing for the ‘‘foo’’ objects introduced in Section 2.1.

The constructor and destructor routines are:

void

foo_constructor(void *buf, int size)

{

struct foo *foo = buf;

mutex_init(&foo->foo_lock, ...);

cv_init(&foo->foo_cv, ...);

foo->foo_refcnt = 0;

foo->foo_barlist = NULL;

}

void

foo_destructor(void *buf, int size)

{

struct foo *foo = buf;

ASSERT(foo->foo_barlist == NULL);

ASSERT(foo->foo_refcnt == 0);

cv_destroy(&foo->foo_cv);

mutex_destroy(&foo->foo_lock);

}

剩余11页未读，继续阅读

redkowl

粉丝: 6
资源: 7

会员权益专享

The Slab Allocator An Object-Caching Kernel Memory Allocator

评论0

会员权益专享

最新资源

The Slab Allocator An Object-Caching Kernel Memory Allocator

评论0

linux slab分配器分析

Linux2.6+slab内核缓冲区管理

linux slab算法

linux slob slab slub allocator

Python库 | slab-1.0.2-py3-none-any.whl

Sparrow OS 设计文档连载七：Slab Memory Allocator

Caching allocator

操作系统slab allocator

/sys/kernel/slab下是什么文件

linux 内存泄漏命名

arcgisfonts/josefin-slab-bold/24064-24319.pbf

linux中分页就是slab吗

proc/meminfo里边有什么信息

slabAllocatorNew(slabSize, 4, 15);含义

linux操作系统meminfo各个字段的含义是什么？

/proc/meminfo 中 kernel 部分的参数含义

linux内存分配slab

slab占用过高 排查

内核slab相同的颜色

会员权益专享

最新资源

slab占用过高排查