lib/idr.c
void __init idr_init_cache(void)
{
idr_layer_cache = kmem_cache_create("idr_layer_cache",
sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
}
idr_layer 구조체를 할당하기 위한 전용 slub 캐시를 생성한다.
radix tree를 사용하여 정수 ID를 관리하고 이에 연결된 포인터 값을 반환한다. 다음은 리눅스 IDR의 특징이다.
다음 그림은 IDR이 레이어별로 관리되는 모습을 보여준다.
다음 그림은 256~511까지의 ID와 1025의 ID가 할당되어 관리되는 모습을 보여준다.
include/linux/idr.h
#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
주어진 이름으로 idr 구조체를 선언하고 초기화한다.
include/linux/idr.h
#define IDR_INIT(name) \
{ \
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \
}
주어진 이름의 idr 구조체를 초기화한다.
idr_init()
/**
* idr_init - initialize idr handle
* @idp: idr handle
*
* This function is use to set up the handle (@idp) that you will pass
* to the rest of the functions.
*/
void idr_init(struct idr *idp)
{
memset(idp, 0, sizeof(struct idr));
spin_lock_init(&idp->lock);
}
EXPORT_SYMBOL(idr_init);
idr 구조체 멤버 변수를 모두 0으로 초기화하고 lock 멤버만 spinlock 초기화한다.
lib/idr.c
/**
* idr_preload - preload for idr_alloc()
* @gfp_mask: allocation mask to use for preloading
*
* Preload per-cpu layer buffer for idr_alloc(). Can only be used from
* process context and each idr_preload() invocation should be matched with
* idr_preload_end(). Note that preemption is disabled while preloaded.
*
* The first idr_alloc() in the preloaded section can be treated as if it
* were invoked with @gfp_mask used for preloading. This allows using more
* permissive allocation masks for idrs protected by spinlocks.
*
* For example, if idr_alloc() below fails, the failure can be treated as
* if idr_alloc() were called with GFP_KERNEL rather than GFP_NOWAIT.
*
* idr_preload(GFP_KERNEL);
* spin_lock(lock);
*
* id = idr_alloc(idr, ptr, start, end, GFP_NOWAIT);
*
* spin_unlock(lock);
* idr_preload_end();
* if (id < 0)
* error;
*/
void idr_preload(gfp_t gfp_mask)
{
/*
* Consuming preload buffer from non-process context breaks preload
* allocation guarantee. Disallow usage from those contexts.
*/
WARN_ON_ONCE(in_interrupt());
might_sleep_if(gfp_mask & __GFP_WAIT);
preempt_disable();
/*
* idr_alloc() is likely to succeed w/o full idr_layer buffer and
* return value from idr_alloc() needs to be checked for failure
* anyway. Silently give up if allocation fails. The caller can
* treat failures from idr_alloc() as if idr_alloc() were called
* with @gfp_mask which should be enough.
*/
while (__this_cpu_read(idr_preload_cnt) < MAX_IDR_FREE) {
struct idr_layer *new;
preempt_enable();
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
preempt_disable();
if (!new)
break;
/* link the new one to per-cpu preload list */
new->ary[0] = __this_cpu_read(idr_preload_head);
__this_cpu_write(idr_preload_head, new);
__this_cpu_inc(idr_preload_cnt);
}
}
EXPORT_SYMBOL(idr_preload);
idr preload 버퍼에 8(32bit 시스템 기준)개의 idr_layer 엔트리를 미리 할당해둔다. 이 idr 프리로드 버퍼는 idr_alloc() 함수가 필요로하는 idr_layer를 미리 준비하여 필요할 때마다 최대한 짧은 시간에 제공하여 preemption disable 구간에서 동작하는 idr_alloc() 함수를 위해 preemption disable 기간을 최대한 줄이기 위해 사용된다.
다음 그림은 idr_preload() 함수를 idr preload 버퍼에 미리 8(32bit 시스템)개의 idr_layer 구조체들을 할당해놓은 것을 보여준다.
include/linux/idr.h
/**
* idr_preload_end - end preload section started with idr_preload()
*
* Each idr_preload() should be matched with an invocation of this
* function. See idr_preload() for details.
*/
static inline void idr_preload_end(void)
{
preempt_enable();
}
idr_alloc()이 끝났으므로 preemption을 enable하여 이제 선점 가능한 상태도 바꾼다.
lib/idr.c
/**
* idr_alloc - allocate new idr entry
* @idr: the (initialized) idr
* @ptr: pointer to be associated with the new id
* @start: the minimum id (inclusive)
* @end: the maximum id (exclusive, <= 0 for max)
* @gfp_mask: memory allocation flags
*
* Allocate an id in [start, end) and associate it with @ptr. If no ID is
* available in the specified range, returns -ENOSPC. On memory allocation
* failure, returns -ENOMEM.
*
* Note that @end is treated as max when <= 0. This is to always allow
* using @start + N as @end as long as N is inside integer range.
*
* The user is responsible for exclusively synchronizing all operations
* which may modify @idr. However, read-only accesses such as idr_find()
* or iteration can be performed under RCU read lock provided the user
* destroys @ptr in RCU-safe way after removal from idr.
*/
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
{
int max = end > 0 ? end - 1 : INT_MAX; /* inclusive upper limit */
struct idr_layer *pa[MAX_IDR_LEVEL + 1];
int id;
might_sleep_if(gfpflags_allow_blocking(gfp_mask));
/* sanity checks */
if (WARN_ON_ONCE(start < 0))
return -EINVAL;
if (unlikely(max < start))
return -ENOSPC;
/* allocate id */
id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL);
if (unlikely(id < 0))
return id;
if (unlikely(id > max))
return -ENOSPC;
idr_fill_slot(idr, ptr, id, pa);
return id;
}
EXPORT_SYMBOL_GPL(idr_alloc);
start ~ (end-1) 정수 범위내에서 빈 id를 찾아 ptr을 저장하고 id를 반환한다. end가 0인 경우 시스템 최대 정수값인 INT_MAX로 지정된다.
다음 그림은 0~65535 ID까지 full되어 2단계 레이어로 관리되고 있는 상태에서 65536번의 IDR이 추가 할당되어 3단계 레이어로 확장되는 모습을 보여준다.
lib/idr.c
static int idr_get_empty_slot(struct idr *idp, int starting_id,
struct idr_layer **pa, gfp_t gfp_mask,
struct idr *layer_idr)
{
struct idr_layer *p, *new;
int layers, v, id;
unsigned long flags;
id = starting_id;
build_up:
p = idp->top;
layers = idp->layers;
if (unlikely(!p)) {
if (!(p = idr_layer_alloc(gfp_mask, layer_idr)))
return -ENOMEM;
p->layer = 0;
layers = 1;
}
/*
* Add a new layer to the top of the tree if the requested
* id is larger than the currently allocated space.
*/
while (id > idr_max(layers)) {
layers++;
if (!p->count) {
/* special case: if the tree is currently empty,
* then we grow the tree by moving the top node
* upwards.
*/
p->layer++;
WARN_ON_ONCE(p->prefix);
continue;
}
if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) {
/*
* The allocation failed. If we built part of
* the structure tear it down.
*/
spin_lock_irqsave(&idp->lock, flags);
for (new = p; p && p != idp->top; new = p) {
p = p->ary[0];
new->ary[0] = NULL;
new->count = 0;
bitmap_clear(new->bitmap, 0, IDR_SIZE);
__move_to_free_list(idp, new);
}
spin_unlock_irqrestore(&idp->lock, flags);
return -ENOMEM;
}
new->ary[0] = p;
new->count = 1;
new->layer = layers-1;
new->prefix = id & idr_layer_prefix_mask(new->layer);
if (bitmap_full(p->bitmap, IDR_SIZE))
__set_bit(0, new->bitmap);
p = new;
}
rcu_assign_pointer(idp->top, p);
idp->layers = layers;
v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr);
if (v == -EAGAIN)
goto build_up;
return(v);
}
start ~ end-1 까지 비어있는 ID를 찾아 반환한다. 이 과정에서 만일 레이어 확장(tree depth)이 필요한 경우 생성하게한다.
lib/idr.c
/**
* idr_layer_alloc - allocate a new idr_layer
* @gfp_mask: allocation mask
* @layer_idr: optional idr to allocate from
*
* If @layer_idr is %NULL, directly allocate one using @gfp_mask or fetch
* one from the per-cpu preload buffer. If @layer_idr is not %NULL, fetch
* an idr_layer from @idr->id_free.
*
* @layer_idr is to maintain backward compatibility with the old alloc
* interface - idr_pre_get() and idr_get_new*() - and will be removed
* together with per-pool preload buffer.
*/
static struct idr_layer *idr_layer_alloc(gfp_t gfp_mask, struct idr *layer_idr)
{
struct idr_layer *new;
/* this is the old path, bypass to get_from_free_list() */
if (layer_idr)
return get_from_free_list(layer_idr);
/*
* Try to allocate directly from kmem_cache. We want to try this
* before preload buffer; otherwise, non-preloading idr_alloc()
* users will end up taking advantage of preloading ones. As the
* following is allowed to fail for preloaded cases, suppress
* warning this time.
*/
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask | __GFP_NOWARN);
if (new)
return new;
/*
* Try to fetch one from the per-cpu preload buffer if in process
* context. See idr_preload() for details.
*/
if (!in_interrupt()) {
preempt_disable();
new = __this_cpu_read(idr_preload_head);
if (new) {
__this_cpu_write(idr_preload_head, new->ary[0]);
__this_cpu_dec(idr_preload_cnt);
new->ary[0] = NULL;
}
preempt_enable();
if (new)
return new;
}
/*
* Both failed. Try kmem_cache again w/o adding __GFP_NOWARN so
* that memory allocation failure warning is printed as intended.
*/
return kmem_cache_zalloc(idr_layer_cache, gfp_mask);
}
idr preload 버퍼 또는 idr_layer_cache에서 idr_layer 구조체를 할당받아온다.
lib/idr.c
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p;
unsigned long flags;
spin_lock_irqsave(&idp->lock, flags);
if ((p = idp->id_free)) {
idp->id_free = p->ary[0];
idp->id_free_cnt--;
p->ary[0] = NULL;
}
spin_unlock_irqrestore(&idp->lock, flags);
return(p);
}
id_free 리스트에 엔트리가 있는 경우 리스트에서 엔트리를 제거하고 그 엔트리를 반환한다.
lib/idr.c
/* the maximum ID which can be allocated given idr->layers */
static int idr_max(int layers)
{
int bits = min_t(int, layers * IDR_BITS, MAX_IDR_SHIFT);
return (1 << bits) - 1;
}
주어진 레이어에서 할당받을 수 있는 max ID(positive integer)를 알아온다.
lib/idr.c
/* only called when idp->lock is held */
static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
{
p->ary[0] = idp->id_free;
idp->id_free = p;
idp->id_free_cnt++;
}
엔트리를 id_free 리스트에 추가한다.
lib/idr.c
/*
* Prefix mask for an idr_layer at @layer. For layer 0, the prefix mask is
* all bits except for the lower IDR_BITS. For layer 1, 2 * IDR_BITS, and
* so on.
*/
static int idr_layer_prefix_mask(int layer)
{
return ~idr_max(layer + 1);
}
요청 layer에 대한 prefix 값을 반환한다.
lib/idr.c
/**
* sub_alloc - try to allocate an id without growing the tree depth
* @idp: idr handle
* @starting_id: id to start search at
* @pa: idr_layer[MAX_IDR_LEVEL] used as backtrack buffer
* @gfp_mask: allocation mask for idr_layer_alloc()
* @layer_idr: optional idr passed to idr_layer_alloc()
*
* Allocate an id in range [@starting_id, INT_MAX] from @idp without
* growing its depth. Returns
*
* the allocated id >= 0 if successful,
* -EAGAIN if the tree needs to grow for allocation to succeed,
* -ENOSPC if the id space is exhausted,
* -ENOMEM if more idr_layers need to be allocated.
*/
static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa,
gfp_t gfp_mask, struct idr *layer_idr)
{
int n, m, sh;
struct idr_layer *p, *new;
int l, id, oid;
id = *starting_id;
restart:
p = idp->top;
l = idp->layers;
pa[l--] = NULL;
while (1) {
/*
* We run around this while until we reach the leaf node...
*/
n = (id >> (IDR_BITS*l)) & IDR_MASK;
m = find_next_zero_bit(p->bitmap, IDR_SIZE, n);
if (m == IDR_SIZE) {
/* no space available go back to previous layer. */
l++;
oid = id;
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
/* if already at the top layer, we need to grow */
if (id > idr_max(idp->layers)) {
*starting_id = id;
return -EAGAIN;
}
p = pa[l];
BUG_ON(!p);
/* If we need to go up one layer, continue the
* loop; otherwise, restart from the top.
*/
sh = IDR_BITS * (l + 1);
if (oid >> sh == id >> sh)
continue;
else
goto restart;
}
ID를 할당하되 레이어의 depth를 변경하지 않고 그 범위 내의 하위 레이어 중 할당이 필요한 레이어들을 할당한다. 출력 인수 pa 포인터 배열에는 최상위 레이어부터 id에 해당하는 레이어까지 idr_layer의 포인터 주소를 담는다.
if (m != n) {
sh = IDR_BITS*l;
id = ((id >> sh) ^ n ^ m) << sh;
}
if ((id >= MAX_IDR_BIT) || (id < 0))
return -ENOSPC;
if (l == 0)
break;
/*
* Create the layer below if it is missing.
*/
if (!p->ary[m]) {
new = idr_layer_alloc(gfp_mask, layer_idr);
if (!new)
return -ENOMEM;
new->layer = l-1;
new->prefix = id & idr_layer_prefix_mask(new->layer);
rcu_assign_pointer(p->ary[m], new);
p->count++;
}
pa[l--] = p;
p = p->ary[m];
}
pa[l] = p;
return id;
}
lib/idr.c
/*
* @id and @pa are from a successful allocation from idr_get_empty_slot().
* Install the user pointer @ptr and mark the slot full.
*/
static void idr_fill_slot(struct idr *idr, void *ptr, int id,
struct idr_layer **pa)
{
/* update hint used for lookup, cleared from free_layer() */
rcu_assign_pointer(idr->hint, pa[0]);
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
}
마지막에 ID를 할당한 leaf 노드의 주소를 idr 구조체의 hint 멤버에 대입하고, ary[]배열에 ptr을 저장하고, count를 증가시킨 후 full이된 레이어들의 bitmap을 1로 설정한다.
lib/idr.c
static void idr_mark_full(struct idr_layer **pa, int id)
{
struct idr_layer *p = pa[0];
int l = 0;
__set_bit(id & IDR_MASK, p->bitmap);
/*
* If this layer is full mark the bit in the layer above to
* show that this part of the radix tree is full. This may
* complete the layer above and require walking up the radix
* tree.
*/
while (bitmap_full(p->bitmap, IDR_SIZE)) {
if (!(p = pa[++l]))
break;
id = id >> IDR_BITS;
__set_bit((id & IDR_MASK), p->bitmap);
}
}
마지막에 ID를 할당한 leaf 노드의 bitmap에 id에 해당하는 비트를 1로 설정하여 ID가 할당되었음을 표시한 후, 그 노드부터 최상위 노드중 full된 노드의 상위 노드 bitmap에 해당 비트를 1로 설정한다.
다음 그림은 0xffffff ID를 할당받은 후 idr_mark_full() 함수에 의해 각 bitmap에 full 처리되는 모습을 보여준다.
idr_remove()
lib/idr.c
/**
* idr_remove - remove the given id and free its slot
* @idp: idr handle
* @id: unique key
*/
void idr_remove(struct idr *idp, int id)
{
struct idr_layer *p;
struct idr_layer *to_free;
if (id < 0)
return;
if (id > idr_max(idp->layers)) {
idr_remove_warning(id);
return;
}
sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
idp->top->ary[0]) {
/*
* Single child at leftmost slot: we can shrink the tree.
* This level is not needed anymore since when layers are
* inserted, they are inserted at the top of the existing
* tree.
*/
to_free = idp->top;
p = idp->top->ary[0];
rcu_assign_pointer(idp->top, p);
--idp->layers;
to_free->count = 0;
bitmap_clear(to_free->bitmap, 0, IDR_SIZE);
free_layer(idp, to_free);
}
}
EXPORT_SYMBOL(idr_remove);
할당한 id를 제거하고, 제거하는 중에 empty된 레이어들은 제거된다. 필요에 따라 레이어 depth 까지도 줄어든다.
다음 그림은 3단계의 레이어에서 65536번 id를 삭제하면서 레이어들이 삭제되고 tree depth가 줄어드는 과정을 보여준다.
lib/idr.c
static void sub_remove(struct idr *idp, int shift, int id)
{
struct idr_layer *p = idp->top;
struct idr_layer **pa[MAX_IDR_LEVEL + 1];
struct idr_layer ***paa = &pa[0];
struct idr_layer *to_free;
int n;
*paa = NULL;
*++paa = &idp->top;
while ((shift > 0) && p) {
n = (id >> shift) & IDR_MASK;
__clear_bit(n, p->bitmap);
*++paa = &p->ary[n];
p = p->ary[n];
shift -= IDR_BITS;
}
n = id & IDR_MASK;
if (likely(p != NULL && test_bit(n, p->bitmap))) {
__clear_bit(n, p->bitmap);
RCU_INIT_POINTER(p->ary[n], NULL);
to_free = NULL;
while(*paa && ! --((**paa)->count)){
if (to_free)
free_layer(idp, to_free);
to_free = **paa;
**paa-- = NULL;
}
if (!*paa)
idp->layers = 0;
if (to_free)
free_layer(idp, to_free);
} else
idr_remove_warning(id);
}
tree depth를 줄이지 않은 상태에서 삭제할 id에 관여되는 레이어들 중 empty되는 레이어들을 연결에서 제거하고 할당을 해제한다.
static inline void free_layer(struct idr *idr, struct idr_layer *p)
{
if (idr->hint == p)
RCU_INIT_POINTER(idr->hint, NULL);
call_rcu(&p->rcu_head, idr_layer_rcu_free);
}
idr->hint가 삭제할 p를 가리키는 경우 hint에 null을 대입한다 그런 후 rcu 기법으로 idr_layer_rcu_free 함수를 호출하여 해당 레이어를 해제하게 한다.
lib/idr.c
static void idr_layer_rcu_free(struct rcu_head *head)
{
struct idr_layer *layer;
layer = container_of(head, struct idr_layer, rcu_head);
kmem_cache_free(idr_layer_cache, layer);
}
요청된 idr_layer를 해제한다.
lib/idr.c
/**
* idr_destroy - release all cached layers within an idr tree
* @idp: idr handle
*
* Free all id mappings and all idp_layers. After this function, @idp is
* completely unused and can be freed / recycled. The caller is
* responsible for ensuring that no one else accesses @idp during or after
* idr_destroy().
*
* A typical clean-up sequence for objects stored in an idr tree will use
* idr_for_each() to free all objects, if necessary, then idr_destroy() to
* free up the id mappings and cached idr_layers.
*/
void idr_destroy(struct idr *idp)
{
__idr_remove_all(idp);
while (idp->id_free_cnt) {
struct idr_layer *p = get_from_free_list(idp);
kmem_cache_free(idr_layer_cache, p);
}
}
EXPORT_SYMBOL(idr_destroy);
모든 idr 레이어를 삭제시키고 id_free 리스트에 담겨있는 할당 대기중인 레이어들을 해제한다.
lib/idr.c
static void __idr_remove_all(struct idr *idp)
{
int n, id, max;
int bt_mask;
struct idr_layer *p;
struct idr_layer *pa[MAX_IDR_LEVEL + 1];
struct idr_layer **paa = &pa[0];
n = idp->layers * IDR_BITS;
*paa = idp->top;
RCU_INIT_POINTER(idp->top, NULL);
max = idr_max(idp->layers);
id = 0;
while (id >= 0 && id <= max) {
p = *paa;
while (n > IDR_BITS && p) {
n -= IDR_BITS;
p = p->ary[(id >> n) & IDR_MASK];
*++paa = p;
}
bt_mask = id;
id += 1 << n;
/* Get the highest bit that the above add changed from 0->1. */
while (n < fls(id ^ bt_mask)) {
if (*paa)
free_layer(idp, *paa);
n += IDR_BITS;
--paa;
}
}
idp->layers = 0;
}
idr 레이어를 모두 해제한다.
include/linux/idr.h
struct idr_layer {
int prefix; /* the ID prefix of this idr_layer */
int layer; /* distance from leaf */
struct idr_layer __rcu *ary[1<<IDR_BITS];
int count; /* When zero, we can release it */
union {
/* A zero bit means "space here" */
DECLARE_BITMAP(bitmap, IDR_SIZE);
struct rcu_head rcu_head;
};
};
include/linux/idr.h
struct idr {
struct idr_layer __rcu *hint; /* the last layer allocated from */
struct idr_layer __rcu *top;
int layers; /* only valid w/o concurrent changes */
int cur; /* current pos for cyclic allocation */
spinlock_t lock;
int id_free_cnt;
struct idr_layer *id_free;
};
<kernel v5.0>
커널에서는 단편화 문제를 유발하는 high order 페이지 할당의 사용을 매우 꺼려한다. 따라서 사이즈가 큰 페이지 할당이 필요하지만 빈번한 할당/해제를 하지 않는 경우에 한해 여러 개의 싱글(order 0) 페이지들을 사용하여 연속된 가상 주소 공간에 모아 매핑하는 방법을 사용한다. 이러한 매핑 방법을 vmap(Virtually contiguous memory area mapping)이라고 한다.
vmap을 사용하여 다음 2가지의 주소 공간에 메모리를 할당하는 api는 다음과 같다.
VMALLOC 가상 주소 공간의 빈 공간 검색을 위해 RB 트리 및 리스트 자료 구조를 동시에 사용한다.
다음 그림은 vmalloc 가상 주소 공간내에서 VM 영역들이 RB 트리 및 리스트에서 관리되고 있는 모습을 보여준다.
위의 자료 구조를 사용하여 vmalloc의 공간을 관리하는 항목은 다음과 같다.
다음 그림은 VM 영역이 vunmap()에 의해 Lazy TLB 플러시 상태로 변화하고, 그 후 purge될 때 실제 TLB 플러시 처리되는 과정을 보여준다.
vmap() 대체 api로 per-cpu map 기반의 api들이 소개되었다. 이 API는 아직 많은 드라이버에 적용되어 사용하지는 않고 일부 드라이버들 에서만 사용하고 있다.
vmap() 함수를 사용하기 위해서 매핑에 사용할 싱글(order 0) 페이지 단위의 물리 메모리 정보들을 페이지 디스크립터 배열로 구성하여 요청한다. 그러면 vmalloc 가상 주소 공간의 빈 자리를 찾아 페이지들을 주어진 매핑 속성으로 매핑하고 매핑된 가상 시작 주소를 반환한다.
다음 그림은 vmap() 함수에 대해 연관 함수들과의 처리 흐름을 보여준다.
mm/vmalloc.c
/** * vmap - map an array of pages into virtually contiguous space * @pages: array of page pointers * @count: number of pages to map * @flags: vm_area->flags * @prot: page protection for the mapping * * Maps @count pages from @pages into contiguous kernel virtual * space. */
void *vmap(struct page **pages, unsigned int count,
unsigned long flags, pgprot_t prot)
{
struct vm_struct *area;
unsigned long size; /* In bytes */
might_sleep();
if (count > totalram_pages())
return NULL;
size = (unsigned long)count << PAGE_SHIFT;
area = get_vm_area_caller(size, flags, __builtin_return_address(0));
if (!area)
return NULL;
if (map_vm_area(area, prot, pages)) {
vunmap(area->addr);
return NULL;
}
return area->addr;
}
EXPORT_SYMBOL(vmap);
연속된 가상 주소 공간에 요청한 물리 페이지들을 매핑하고 매핑한 가상 주소를 반환한다. 실패 시 null을 반환한다.
다음 그림은 요청한 물리 페이지들에 대해 VMALLOC 가상 주소 공간에서 빈 공간을 찾아 매핑을 하는 모습을 보여준다.
mm/vmalloc.c
struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags,
const void *caller)
{
return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END,
NUMA_NO_NODE, GFP_KERNEL, caller);
}
요청한 size(페이지 단위로 정렬된 byte 단위)로 VMALLOC 가상 주소 공간에서 빈 공간을 찾아 VM(vm_area 및 vm_struct) 정보를 구성해온다.
mm/vmalloc.c
static struct vm_struct *__get_vm_area_node(unsigned long size,
unsigned long align, unsigned long flags, unsigned long start,
unsigned long end, int node, gfp_t gfp_mask, const void *caller)
{
struct vmap_area *va;
struct vm_struct *area;
BUG_ON(in_interrupt());
size = PAGE_ALIGN(size);
if (unlikely(!size))
return NULL;
if (flags & VM_IOREMAP)
align = 1ul << clamp_t(int, get_count_order_long(size),
PAGE_SHIFT, IOREMAP_MAX_ORDER);
area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
if (unlikely(!area))
return NULL;
if (!(flags & VM_NO_GUARD))
size += PAGE_SIZE;
va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
if (IS_ERR(va)) {
kfree(area);
return NULL;
}
setup_vmalloc_vm(area, va, flags, caller);
return area;
}
@start ~ @end 가상 주소 공간에서 @align 조건의 @size 만큼의 빈 영역을 찾아 vm을 할당 구성한 후 반환한다.
mm/vmalloc.c -1/2-
/* * Allocate a region of KVA of the specified size and alignment, within the * vstart and vend. */
static struct vmap_area *alloc_vmap_area(unsigned long size,
unsigned long align,
unsigned long vstart, unsigned long vend,
int node, gfp_t gfp_mask)
{
struct vmap_area *va;
struct rb_node *n;
unsigned long addr;
int purged = 0;
struct vmap_area *first;
BUG_ON(!size);
BUG_ON(offset_in_page(size));
BUG_ON(!is_power_of_2(align));
might_sleep();
va = kmalloc_node(sizeof(struct vmap_area),
gfp_mask & GFP_RECLAIM_MASK, node);
if (unlikely(!va))
return ERR_PTR(-ENOMEM);
/*
* Only scan the relevant parts containing pointers to other objects
* to avoid false negatives.
*/
kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask & GFP_RECLAIM_MASK);
retry:
spin_lock(&vmap_area_lock);
/*
* Invalidate cache if we have more permissive parameters.
* cached_hole_size notes the largest hole noticed _below_
* the vmap_area cached in free_vmap_cache: if size fits
* into that hole, we want to scan from vstart to reuse
* the hole instead of allocating above free_vmap_cache.
* Note that __free_vmap_area may update free_vmap_cache
* without updating cached_hole_size or cached_align.
*/
if (!free_vmap_cache ||
size < cached_hole_size ||
vstart < cached_vstart ||
align < cached_align) {
nocache:
cached_hole_size = 0;
free_vmap_cache = NULL;
}
/* record if we encounter less permissive parameters */
cached_vstart = vstart;
cached_align = align;
/* find starting point for our search */
if (free_vmap_cache) {
first = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
addr = ALIGN(first->va_end, align);
if (addr < vstart)
goto nocache;
if (addr + size < addr)
goto overflow;
} else {
addr = ALIGN(vstart, align);
if (addr + size < addr)
goto overflow;
n = vmap_area_root.rb_node;
first = NULL;
while (n) {
struct vmap_area *tmp;
tmp = rb_entry(n, struct vmap_area, rb_node);
if (tmp->va_end >= addr) {
first = tmp;
if (tmp->va_start <= addr)
break;
n = n->rb_left;
} else
n = n->rb_right;
}
if (!first)
goto found;
}
요청한 가상 주소 범위에서 빈 공간을 찾아 va(vmap_area)를 할당 및 구성하고, RB트리 및 리스트에 insert한 후 va(vmap_area)를 반환한다.
mm/vmalloc.c -2/2-
/* from the starting point, walk areas until a suitable hole is found */
while (addr + size > first->va_start && addr + size <= vend) {
if (addr + cached_hole_size < first->va_start)
cached_hole_size = first->va_start - addr;
addr = ALIGN(first->va_end, align);
if (addr + size < addr)
goto overflow;
if (list_is_last(&first->list, &vmap_area_list))
goto found;
first = list_next_entry(first, list);
}
found:
if (addr + size > vend)
goto overflow;
va->va_start = addr;
va->va_end = addr + size;
va->flags = 0;
__insert_vmap_area(va);
free_vmap_cache = &va->rb_node;
spin_unlock(&vmap_area_lock);
BUG_ON(!IS_ALIGNED(va->va_start, align));
BUG_ON(va->va_start < vstart);
BUG_ON(va->va_end > vend);
return va;
overflow:
spin_unlock(&vmap_area_lock);
if (!purged) {
purge_vmap_area_lazy();
purged = 1;
goto retry;
}
if (gfpflags_allow_blocking(gfp_mask)) {
unsigned long freed = 0;
blocking_notifier_call_chain(&vmap_notify_list, 0, &freed);
if (freed > 0) {
purged = 0;
goto retry;
}
}
if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit())
pr_warn("vmap allocation for size %lu failed: use vmalloc=<size> to increase size\n",
size);
kfree(va);
return ERR_PTR(-EBUSY);
}
다음 그림은 매핑을 위해 요청 가상 주소 범위내에서 빈 공간을 찾을 때 먼저 free_vmap_cache 부터 size가 들어갈 빈공간을 검색하는 모습을 보여준다.
다음 그림은 매핑을 위해 요청 가상 주소 범위내에서 빈 공간을 찾을 때 RB 트리로 first vmap_area를 찾고 다시 리스트를 사용하여 size가 들어갈 빈공간을 검색하는 모습을 보여준다.
다음 그림은 free_vmap_cache와 cached_hole_size의 변화를 보여준다.
mm/vmalloc.c
static void __insert_vmap_area(struct vmap_area *va)
{
struct rb_node **p = &vmap_area_root.rb_node;
struct rb_node *parent = NULL;
struct rb_node *tmp;
while (*p) {
struct vmap_area *tmp_va;
parent = *p;
tmp_va = rb_entry(parent, struct vmap_area, rb_node);
if (va->va_start < tmp_va->va_end)
p = &(*p)->rb_left;
else if (va->va_end > tmp_va->va_start)
p = &(*p)->rb_right;
else
BUG();
}
rb_link_node(&va->rb_node, parent, p);
rb_insert_color(&va->rb_node, &vmap_area_root);
/* address-sort this list */
tmp = rb_prev(&va->rb_node);
if (tmp) {
struct vmap_area *prev;
prev = rb_entry(tmp, struct vmap_area, rb_node);
list_add_rcu(&va->list, &prev->list);
} else
list_add_rcu(&va->list, &vmap_area_list);
}
전역 vmap_area_root RB 트리와 전역 vmap_area_list에 vmap_area 엔트리를 insert 한다.
다음 그림은 vmap_area 엔트리를 추가할 때의 모습을 보여준다.
mm/vmalloc.c
int map_vm_area(struct vm_struct *area, pgprot_t prot, struct page **pages)
{
unsigned long addr = (unsigned long)area->addr;
unsigned long end = addr + get_vm_area_size(area);
int err;
err = vmap_page_range(addr, end, prot, pages);
return err > 0 ? 0 : err;
}
EXPORT_SYMBOL_GPL(map_vm_area);
요청한 vm_struct 정보에 담긴 가상 주소 범위에 매핑한다.
include/linux/vmalloc.h
static inline size_t get_vm_area_size(const struct vm_struct *area)
{
if (!(area->flags & VM_NO_GUARD))
/* return actual size without guard page */
return area->size - PAGE_SIZE;
else
return area->size;
}
영역이 사용하는 페이지 수를 반환한다.
mm/vmalloc.c
static int vmap_page_range(unsigned long start, unsigned long end,
pgprot_t prot, struct page **pages)
{
int ret;
ret = vmap_page_range_noflush(start, end, prot, pages);
flush_cache_vmap(start, end);
return ret;
}
요청한 가상 주소 범위를 매핑하고 그 공간을 flush한다.
mm/vmalloc.c
/* * Set up page tables in kva (addr, end). The ptes shall have prot "prot", and * will have pfns corresponding to the "pages" array. * * Ie. pte at addr+N*PAGE_SIZE shall point to pfn corresponding to pages[N] */
static int vmap_page_range_noflush(unsigned long start, unsigned long end,
pgprot_t prot, struct page **pages)
{
pgd_t *pgd;
unsigned long next;
unsigned long addr = start;
int err = 0;
int nr = 0;
BUG_ON(addr >= end);
pgd = pgd_offset_k(addr);
do {
next = pgd_addr_end(addr, end);
err = vmap_p4d_range(pgd, addr, next, prot, pages, &nr);
if (err)
return err;
} while (pgd++, addr = next, addr != end);
return nr;
}
요청 가상 주소 범위에 해당하는 커널 페이지 테이블을 **pages 와 속성 정보를 사용하여 매핑한다.
arch/arm/include/asm/cacheflush.h()
/*
* flush_cache_vmap() is used when creating mappings (eg, via vmap,
* vmalloc, ioremap etc) in kernel space for pages. On non-VIPT
* caches, since the direct-mappings of these pages may contain cached
* data, we need to do a full cache flush to ensure that writebacks
* don't corrupt data placed into these pages via the new mappings.
*/
static inline void flush_cache_vmap(unsigned long start, unsigned long end)
{
if (!cache_is_vipt_nonaliasing())
flush_cache_all();
else
/*
* set_pte_at() called from vmap_pte_range() does not
* have a DSB after cleaning the cache line.
*/
dsb(ishst);
}
요청한 가상 주소 범위에 대해 flush를 한다.
arch/arm64/include/asm/cacheflush.h
/* * Not required on AArch64 (PIPT or VIPT non-aliasing D-cache). */
static inline void flush_cache_vmap(unsigned long start, unsigned long end)
{
}
ARM64 에서는 vmap 매핑을 위해 캐시를 flush하지 않는다.
mm/vmalloc.c
static void setup_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va,
unsigned long flags, const void *caller)
{
spin_lock(&vmap_area_lock);
vm->flags = flags;
vm->addr = (void *)va->va_start;
vm->size = va->va_end - va->va_start;
vm->caller = caller;
va->vm = vm;
va->flags |= VM_VM_AREA;
spin_unlock(&vmap_area_lock);
}
vm_struct 및 vmap_area에 정보를 설정한다.
mm/vmalloc.c
/** * vunmap - release virtual mapping obtained by vmap() * @addr: memory base address * * Free the virtually contiguous memory area starting at @addr, * which was created from the page array passed to vmap(). * * Must not be called in interrupt context. */
void vunmap(const void *addr)
{
BUG_ON(in_interrupt());
might_sleep();
if (addr)
__vunmap(addr, 0);
}
EXPORT_SYMBOL(vunmap);
vmap() 함수로 vmalloc 주소 공간에 매핑한 가상 주소 영역의 매핑을 해제한다. 다만 물리 페이지는 할당 해제하지 않는다.
다음 그림은 vunmap() 함수에 대해 연관 함수들과의 처리 흐름을 보여준다.
다음 그림은 vummap() 함수가 요청한 가상 주소로 vmap_area()를 찾아 그에 해당하는 매핑을 삭제하는 모습을 보여준다.
mm/vmalloc.c
static void __vunmap(const void *addr, int deallocate_pages)
{
struct vm_struct *area;
if (!addr)
return;
if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n",
addr))
return;
area = find_vmap_area((unsigned long)addr)->vm;
if (unlikely(!area)) {
WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
addr);
return;
}
debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
remove_vm_area(addr);
if (deallocate_pages) {
int i;
for (i = 0; i < area->nr_pages; i++) {
struct page *page = area->pages[i];
BUG_ON(!page);
__free_pages(page, 0);
}
kvfree(area->pages);
}
kfree(area);
return;
}
요청 가상 주소로 vm 정보를 찾아 매핑을 제거하고 요청에 따라 각 페이지들을 해제하여 버디 시스템으로 돌려준다.
mm/vmalloc.c
/** * remove_vm_area - find and remove a continuous kernel virtual area * @addr: base address * * Search for the kernel VM area starting at @addr, and remove it. * This function returns the found VM area, but using it is NOT safe * on SMP machines, except for its size or flags. */
struct vm_struct *remove_vm_area(const void *addr)
{
struct vmap_area *va;
might_sleep();
va = find_vmap_area((unsigned long)addr);
if (va && va->flags & VM_VM_AREA) {
struct vm_struct *vm = va->vm;
spin_lock(&vmap_area_lock);
va->vm = NULL;
va->flags &= ~VM_VM_AREA;
va->flags |= VM_LAZY_FREE;
spin_unlock(&vmap_area_lock);
kasan_free_shadow(vm);
free_unmap_vmap_area(va);
return vm;
}
return NULL;
}
요청 가상 주소를 RB 트리 vmap_area_root에 등록되어 있는 vmap_area 정보에서 검색하여 매치된 vmap_area 정보를 제거하고 매핑을 해제 요청한 후 vm_struct 정보를 알아온다.
mm/vmalloc.c
static struct vmap_area *find_vmap_area(unsigned long addr)
{
struct vmap_area *va;
spin_lock(&vmap_area_lock);
va = __find_vmap_area(addr);
spin_unlock(&vmap_area_lock);
return va;
}
vmap_area lock으로 보호한 후 요청 가상 주소로 vmap_area 정보를 찾아온다. 못찾은 경우 null을 반환한다.
mm/vmalloc.c
static struct vmap_area *__find_vmap_area(unsigned long addr)
{
struct rb_node *n = vmap_area_root.rb_node;
while (n) {
struct vmap_area *va;
va = rb_entry(n, struct vmap_area, rb_node);
if (addr < va->va_start)
n = n->rb_left;
else if (addr >= va->va_end)
n = n->rb_right;
else
return va;
}
return NULL;
}
요청 가상 주소로 vmap_area 정보를 찾아온다. 못찾은 경우 null을 반환한다.
mm/vmalloc.c
/* * Free and unmap a vmap area */
static void free_unmap_vmap_area(struct vmap_area *va)
{
flush_cache_vunmap(va->va_start, va->va_end);
unmap_vmap_area(va);
if (debug_pagealloc_enabled())
flush_tlb_kernel_range(va->va_start, va->va_end);
free_vmap_area_noflush(va);
}
아키텍처에 따라 지정된 가상 주소 범위의 데이타 캐시를 비운후 해당 영역의 매핑을 해제한다.
arch/arm/include/asm/cacheflush.h
static inline void flush_cache_vunmap(unsigned long start, unsigned long end)
{
if (!cache_is_vipt_nonaliasing())
flush_cache_all();
}
아키텍처의 데이타 캐시가 vivt 타입이거나 vipt aliasing인 경우 캐시를 모두 비우게 한다.
arch/arm64/include/asm/cacheflush.h
static inline void flush_cache_vunmap(unsigned long start, unsigned long end)
{
}
ARM64 에서는 vmap 매핑 해제를 위해 캐시를 flush하지 않는다.
mm/vmalloc.c
/* * Free and unmap a vmap area, caller ensuring flush_cache_vunmap had been * called for the correct range previously. */
static void free_unmap_vmap_area_noflush(struct vmap_area *va)
{
unmap_vmap_area(va);
free_vmap_area_noflush(va);
}
vmap_area가 사용하는 가상 주소 영역의 매핑을 커널 페이지 테이블에서 해제한다. 그런 후 vmap_area를 곧바로 삭제하지 않고 purge_list에 추가한다.
mm/vmalloc.c
/* * Clear the pagetable entries of a given vmap_area */
static void unmap_vmap_area(struct vmap_area *va)
{
vunmap_page_range(va->va_start, va->va_end);
}
vmap_area의 가상 주소 영역의 매핑을 커널 페이지 테이블에서 해제한다.
mm/vmalloc.c
static void vunmap_page_range(unsigned long addr, unsigned long end)
{
pgd_t *pgd;
unsigned long next;
BUG_ON(addr >= end);
pgd = pgd_offset_k(addr);
do {
next = pgd_addr_end(addr, end);
if (pgd_none_or_clear_bad(pgd))
continue;
vunmap_p4d_range(pgd, addr, next);
} while (pgd++, addr = next, addr != end);
}
요청 가상 주소 범위의 매핑을 커널 페이지 테이블에서 해제한다.
mm/vmalloc.c
/* * Free a vmap area, caller ensuring that the area has been unmapped * and flush_cache_vunmap had been called for the correct range * previously. */
static void free_vmap_area_noflush(struct vmap_area *va)
{
int nr_lazy;
nr_lazy = atomic_add_return((va->va_end - va->va_start) >> PAGE_SHIFT,
&vmap_lazy_nr);
/* After this point, we may free va at any time */
llist_add(&va->purge_list, &vmap_purge_list);
if (unlikely(nr_lazy > lazy_max_pages()))
try_purge_vmap_area_lazy();
}
vmap_area를 곧바로 삭제하지 않고 VM_LAZY_FREE 플래그를 설정하여 lazy TLB 플러시 요청한다. 그 후 페이지 수가 일정량을 초과하는 경우 purge 처리를 수행한다.
mm/vmalloc.c
/* * lazy_max_pages is the maximum amount of virtual address space we gather up * before attempting to purge with a TLB flush. * * There is a tradeoff here: a larger number will cover more kernel page tables * and take slightly longer to purge, but it will linearly reduce the number of * global TLB flushes that must be performed. It would seem natural to scale * this number up linearly with the number of CPUs (because vmapping activity * could also scale linearly with the number of CPUs), however it is likely * that in practice, workloads might be constrained in other ways that mean * vmap activity will not scale linearly with CPUs. Also, I want to be * conservative and not introduce a big latency on huge systems, so go with * a less aggressive log scale. It will still be an improvement over the old * code, and it will be simple to change the scale factor if we find that it * becomes a problem on bigger systems. */
static unsigned long lazy_max_pages(void)
{
unsigned int log;
log = fls(num_online_cpus());
return log * (32UL * 1024 * 1024 / PAGE_SIZE);
}
TLB lazy된 페이지들의 purge 처리를 위해 필요한 페이지 수를 산출한다.
mm/vmalloc.c
/* * Kick off a purge of the outstanding lazy areas. Don't bother if somebody * is already purging. */
static void try_purge_vmap_area_lazy(void)
{
if (mutex_trylock(&vmap_purge_lock)) {
__purge_vmap_area_lazy(ULONG_MAX, 0);
mutex_unlock(&vmap_purge_lock);
}
}
Lazy TLB 플러시 요청된 vmap_area들을 제거하고 전체 가상 주소 범위의 TLB flush를 수행한다.
mm/vmalloc.c
/* * Purges all lazily-freed vmap areas. */
static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
{
struct llist_node *valist;
struct vmap_area *va;
struct vmap_area *n_va;
bool do_free = false;
lockdep_assert_held(&vmap_purge_lock);
valist = llist_del_all(&vmap_purge_list);
llist_for_each_entry(va, valist, purge_list) {
if (va->va_start < start)
start = va->va_start;
if (va->va_end > end)
end = va->va_end;
do_free = true;
}
if (!do_free)
return false;
flush_tlb_kernel_range(start, end);
spin_lock(&vmap_area_lock);
llist_for_each_entry_safe(va, n_va, valist, purge_list) {
int nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
__free_vmap_area(va);
atomic_sub(nr, &vmap_lazy_nr);
cond_resched_lock(&vmap_area_lock);
}
spin_unlock(&vmap_area_lock);
return true;
}
Lazy TLB 플러시 요청된 vmap_area들을 모두 제거하고 @start ~ @end 범위의 TLB flush를 수행한다.
mm/vmalloc.c
static void __free_vmap_area(struct vmap_area *va)
{
BUG_ON(RB_EMPTY_NODE(&va->rb_node));
if (free_vmap_cache) {
if (va->va_end < cached_vstart) {
free_vmap_cache = NULL;
} else {
struct vmap_area *cache;
cache = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
if (va->va_start <= cache->va_start) {
free_vmap_cache = rb_prev(&va->rb_node);
/*
* We don't try to update cached_hole_size or
* cached_align, but it won't go very wrong.
*/
}
}
}
rb_erase(&va->rb_node, &vmap_area_root);
RB_CLEAR_NODE(&va->rb_node);
list_del_rcu(&va->list);
/*
* Track the highest possible candidate for pcpu area
* allocation. Areas outside of vmalloc area can be returned
* here too, consider only end addresses which fall inside
* vmalloc area proper.
*/
if (va->va_end > VMALLOC_START && va->va_end <= VMALLOC_END)
vmap_area_pcpu_hole = max(vmap_area_pcpu_hole, va->va_end);
kfree_rcu(va, rcu_head);
}
요청한 vmap_area를 RB 트리 vmap_area_root와 vmap_area_list에서 제거한 후 해제한다.
<kernel v5.0>
커널에서 주로 큰 사이즈의 연속된 가상 주소 공간을 할당 받아 사용한다. 물리적으로 연속되지 않는 공간이므로 dma 버퍼로는 사용할 수 없다.
가상 주소가 연속된 큰 사이즈의 커널 메모리의 할당이 필요한 경우 사용된다. vmalloc을 이용한 커널 메모리의 할당은 다음과 같은 특징이 있다.
할당 및 해제 관련한 주요 API는 다음과 같다.
버디 시스템을 사용하는 페이지 할당자로 부터 vmalloc() 함수가 요청한 size가 들어갈 수 있을만큼 싱글 페이지들을 할당받아 이를 모아 vmalloc 가상 주소 공간의 빈 공간을 찾아 각 싱글 페이지를 순차적으로 빈 자리에 매핑하고 그 매핑된 가상 주소를 반환한다.
다음 그림은 vmalloc 가상 주소 공간의 위치를 보여준다.
vmalloc() 함수를 통해 요청한 사이즈가 들어갈 수 있는 싱글 페이지들을 가져와 vmalloc 가상 주소 영역의 빈자리를 찾아 연속되도록 한꺼번에 매핑하는 모습을 보여준다.
커널이 사용하는 연속된 가상 주소 메모리를 할당 받는 메커니즘을 위해 초기화를 수행한다.
다음 그림은 vmalloc_init() 함수의 처리 흐름을 보여준다.
mm/vmalloc.c
void __init vmalloc_init(void)
{
struct vmap_area *va;
struct vm_struct *tmp;
int i;
for_each_possible_cpu(i) {
struct vmap_block_queue *vbq;
struct vfree_deferred *p;
vbq = &per_cpu(vmap_block_queue, i);
spin_lock_init(&vbq->lock);
INIT_LIST_HEAD(&vbq->free);
p = &per_cpu(vfree_deferred, i);
init_llist_head(&p->list);
INIT_WORK(&p->wq, free_work);
}
/* Import existing vmlist entries. */
for (tmp = vmlist; tmp; tmp = tmp->next) {
va = kzalloc(sizeof(struct vmap_area), GFP_NOWAIT);
va->flags = VM_VM_AREA;
va->va_start = (unsigned long)tmp->addr;
va->va_end = va->va_start + tmp->size;
va->vm = tmp;
__insert_vmap_area(va);
}
vmap_area_pcpu_hole = VMALLOC_END;
vmap_initialized = true;
}
vmalloc 공간을 이용할 수 있도록 초기화한다.
mm/vmalloc.c
/** * vmalloc - allocate virtually contiguous memory * @size: allocation size * Allocate enough pages to cover @size from the page level * allocator and map them into contiguous kernel virtual space. * * For tight control over page level allocator and protection flags * use __vmalloc() instead. */
void *vmalloc(unsigned long size)
{
return __vmalloc_node_flags(size, NUMA_NO_NODE,
GFP_KERNEL);
}
EXPORT_SYMBOL(vmalloc);
커널을 위해 @size 만큼의 연속된 가상 주소 공간을 할당받는다. __vmalloc_node_flags() 함수를 이어 호출한다.
다음 그림은 vmalloc() 함수와 관련 함수들간의 처리 흐름을 보여준다.
mm/vmalloc.c
static inline void *__vmalloc_node_flags(unsigned long size,
int node, gfp_t flags)
{
return __vmalloc_node(size, 1, flags, PAGE_KERNEL,
node, __builtin_return_address(0));
}
커널을 위해 요청 노드에서 연속된 가상 메모리를 할당한다.
mm/vmalloc.c
/** * __vmalloc_node - allocate virtually contiguous memory * @size: allocation size * @align: desired alignment * @gfp_mask: flags for the page level allocator * @prot: protection mask for the allocated pages * @node: node to use for allocation or NUMA_NO_NODE * @caller: caller's return address * * Allocate enough pages to cover @size from the page level * allocator with @gfp_mask flags. Map them into contiguous * kernel virtual space, using a pagetable protection of @prot. * * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL * and __GFP_NOFAIL are not supported * * Any use of gfp flags outside of GFP_KERNEL should be consulted * with mm people. * */
static void *__vmalloc_node(unsigned long size, unsigned long align,
gfp_t gfp_mask, pgprot_t prot,
int node, const void *caller)
{
return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
gfp_mask, prot, 0, node, caller);
}
커널을 위해 @node에서 연속된 가상 메모리를 할당하되 가상 주소는 VMALLOC address space의 빈 공간을 사용하여 가상 주소를 매핑하게 한다.
mm/vmalloc.c
/** * __vmalloc_node_range - allocate virtually contiguous memory * @size: allocation size * @align: desired alignment * @start: vm area range start * @end: vm area range end * @gfp_mask: flags for the page level allocator * @prot: protection mask for the allocated pages * @vm_flags: additional vm area flags (e.g. %VM_NO_GUARD) * @node: node to use for allocation or NUMA_NO_NODE * @caller: caller's return address * * Allocate enough pages to cover @size from the page level * allocator with @gfp_mask flags. Map them into contiguous * kernel virtual space, using a pagetable protection of @prot. */
void *__vmalloc_node_range(unsigned long size, unsigned long align,
unsigned long start, unsigned long end, gfp_t gfp_mask,
pgprot_t prot, unsigned long vm_flags, int node,
const void *caller)
{
struct vm_struct *area;
void *addr;
unsigned long real_size = size;
size = PAGE_ALIGN(size);
if (!size || (size >> PAGE_SHIFT) > totalram_pages)
goto fail;
area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNINITIALIZED |
vm_flags, start, end, node, gfp_mask, caller);
if (!area)
goto fail;
addr = __vmalloc_area_node(area, gfp_mask, prot, node);
if (!addr)
return NULL;
/*
* In this function, newly allocated vm_struct has VM_UNINITIALIZED
* flag. It means that vm_struct is not fully initialized.
* Now, it is fully initialized, so remove this flag here.
*/
clear_vm_uninitialized_flag(area);
/*
* A ref_count = 2 is needed because vm_struct allocated in
* __get_vm_area_node() contains a reference to the virtual address of
* the vmalloc'ed block.
*/
kmemleak_vmalloc(area, size, gfp_mask);
return addr;
fail:
warn_alloc_failed(gfp_mask, NULL,
"vmalloc: allocation failure: %lu bytes\n", real_size);
return NULL;
}
요청 노드에서 연속된 가상 메모리를 할당하되 가상 주소는 지정된 범위 이내의 빈 공간을 사용한 가상 주소를 매핑하게 한다.
다음 그림은 vmap_area와 vm_struct가 할당받아 구성되고 필요한 물리 페이지 수 만큼 page descriptor 배열을 할당 받고 그 수 만큼 order 0 페이지들을 할당받아 연결하고 매핑되는 모습을 보여준다.
mm/vmalloc.c
static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
pgprot_t prot, int node)
{
struct page **pages;
unsigned int nr_pages, array_size, i;
const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
const gfp_t alloc_mask = gfp_mask | __GFP_NOWARN;
const gfp_t highmem_mask = (gfp_mask & (GFP_DMA | GFP_DMA32)) ?
0 :
__GFP_HIGHMEM;
nr_pages = get_vm_area_size(area) >> PAGE_SHIFT;
array_size = (nr_pages * sizeof(struct page *));
area->nr_pages = nr_pages;
/* Please note that the recursion is strictly bounded. */
if (array_size > PAGE_SIZE) {
pages = __vmalloc_node(array_size, 1, nested_gfp|highmem_mask,
PAGE_KERNEL, node, area->caller);
} else {
pages = kmalloc_node(array_size, nested_gfp, node);
}
area->pages = pages;
if (!area->pages) {
remove_vm_area(area->addr);
kfree(area);
return NULL;
}
for (i = 0; i < area->nr_pages; i++) {
struct page *page;
if (node == NUMA_NO_NODE)
page = alloc_page(alloc_mask|highmem_mask);
else
page = alloc_pages_node(node, alloc_mask|highmem_mask, 0);
if (unlikely(!page)) {
/* Successfully allocated i pages, free them in __vunmap() */
area->nr_pages = i;
goto fail;
}
area->pages[i] = page;
if (gfpflags_allow_blocking(gfp_mask|highmem_mask))
cond_resched();
}
if (map_vm_area(area, prot, pages))
goto fail;
return area->addr;
fail:
warn_alloc(gfp_mask, NULL,
"vmalloc: allocation failure, allocated %ld of %ld bytes",
(area->nr_pages*PAGE_SIZE), area->size);
vfree(area->addr);
return NULL;
}
vm_struct 정보가 요청하는 가상 주소 영역 만큼 page 디스크립터 배열을 할당받고 싱글 페이지들을 요청 수 만큼 할당하여 연결하고 페이지 테이블에 매핑한다.
mm/vmalloc.c
static void clear_vm_uninitialized_flag(struct vm_struct *vm)
{
/*
* Before removing VM_UNINITIALIZED,
* we should make sure that vm has proper values.
* Pair with smp_rmb() in show_numa_info().
*/
smp_wmb();
vm->flags &= ~VM_UNINITIALIZED;
}
vm 설정이 완료되었음을 나타내기 위해 VM_UNINITIALIZED 플래그를 제거한다.
mm/vmalloc.c
/** * vfree - release memory allocated by vmalloc() * @addr: memory base address * * Free the virtually continuous memory area starting at @addr, as * obtained from vmalloc(), vmalloc_32() or __vmalloc(). If @addr is * NULL, no operation is performed. * * Must not be called in NMI context (strictly speaking, only if we don't * have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling * conventions for vfree() arch-depenedent would be a really bad idea) * * May sleep if called *not* from interrupt context. * * NOTE: assumes that the object at @addr has a size >= sizeof(llist_node) */
void vfree(const void *addr)
{
BUG_ON(in_nmi());
kmemleak_free(addr);
might_sleep_if(!in_interrupt());
if (!addr)
return;
if (unlikely(in_interrupt()))
__vfree_deferred(addr);
else
__vunmap(addr, 1);
}
EXPORT_SYMBOL(vfree);
vmalloc()에 의해 할당되고 매핑된 연속된 가상 주소 메모리를 해제한다.
다음 그림은 vfree() 함수와 관련 함수의 흐름을 보여준다.
mm/vmalloc.c
static void free_work(struct work_struct *w)
{
struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq);
struct llist_node *t, *llnode;
llist_for_each_safe(llnode, t, llist_del_all(&p->list))
__vunmap((void *)llnode, 1);
}
per-cpu vfree_deferred 리스트에 있는 모든 vm(연속된 가상 주소에 매핑된 메모리)들을 해제한다.
다음 페이지로 통합하였습니다.