<kernel v5.0>
유저 프로세스의 힙 또는 스택 메모리 증/감 요청
Heap Manager
user space에서 malloc() 함수를 사용 시 glibc등의 라이브러리에 포함된 힙 메모리 관리자가 힙 pool을 관리한다. 만일 힙 메모리가 더 필요한 경우 커널에게 Posix system call을 통해 유저 anon 메모리 요청을 하게되는데 이 때 커널에서 호출되는 함수는 brk() 또는 mmap()이다.
- M_MMAP_THRESHOLD (128K)
- mallopt() 함수를 사용하여 스레졸드 기준치를 변경할 수 있다.
- 스레졸드 이하의 힙을 확장하려할 때 brk() 함수가 호출되며 이는 mmap()의 간단한 버전으로 anonymouse 타입의 메모리만 취급한다.
- 스레졸드 이상의 힙을 확장하는 경우에는 mmap() 함수가 호출된다.
Custom Heap Manager
대부분의 경우 힙 관리를 위해 C에서는 GNU의 glibc 라이브러리, 그리고 assembly에서는 FASMLIB 라이브러리를 사용하는 것이 쉽고 편하다. 그런데 이러한 라이브러리를 사용하지 않고 특별히 custom 힙 관리자를 사용해야 하는 경우도 있다. 당연히 개발자가 직접 복잡한 스레드들을 위해 특별한 힙 관리자를 만들기 위해 brk() 또는 map() 시스템 콜 함수를 호출하는 custom 힙 메모리 관리자를 작성할 수 있다.
sys_brk()
mm/mmap.c -1/2-
SYSCALL_DEFINE1(brk, unsigned long, brk)
{
unsigned long retval;
unsigned long newbrk, oldbrk, origbrk;
struct mm_struct *mm = current->mm;
struct vm_area_struct *next;
unsigned long min_brk;
bool populate;
bool downgraded = false;
LIST_HEAD(uf);
if (down_write_killable(&mm->mmap_sem))
return -EINTR;
origbrk = mm->brk;
#ifdef CONFIG_COMPAT_BRK
/*
* CONFIG_COMPAT_BRK can still be overridden by setting
* randomize_va_space to 2, which will still cause mm->start_brk
* to be arbitrarily shifted
*/
if (current->brk_randomized)
min_brk = mm->start_brk;
else
min_brk = mm->end_data;
#else
min_brk = mm->start_brk;
#endif
if (brk < min_brk)
goto out;
/*
* Check against rlimit here. If this check is done later after the test
* of oldbrk with newbrk then it can escape the test and let the data
* segment grow beyond its set limit the in case where the limit is
* not page aligned -Ram Gupta
*/
if (check_data_rlimit(rlimit(RLIMIT_DATA), brk, mm->start_brk,
mm->end_data, mm->start_data))
goto out;
newbrk = PAGE_ALIGN(brk);
oldbrk = PAGE_ALIGN(mm->brk);
if (oldbrk == newbrk) {
mm->brk = brk;
goto success;
}
/*
* Always allow shrinking brk.
* __do_munmap() may downgrade mmap_sem to read.
*/
if (brk <= mm->brk) {
int ret;
/*
* mm->brk must to be protected by write mmap_sem so update it
* before downgrading mmap_sem. When __do_munmap() fails,
* mm->brk will be restored from origbrk.
*/
mm->brk = brk;
ret = __do_munmap(mm, newbrk, oldbrk-newbrk, &uf, true);
if (ret < 0) {
mm->brk = origbrk;
goto out;
} else if (ret == 1) {
downgraded = true;
}
goto success;
}
힙(데이터) 영역을 확장하거나 축소한다. 확장 시 anon 유저 페이지로 할당하고, 축소 시 해당 영역을 언매핑 한다.
- 코드 라인 23~28에서 보안 목적으로 user space에 배치되는 힙 위치를 랜덤하게 사용하는데 레거시 libc5 등 호환 목적으로 이 커널 옵션을 사용하여 힙 시작 위치 랜덤 기능을 사용하지 않게 한다.
- “echo 2 > /proc/sys/kernel/randomize_va_space”를 수행하는 경우 힙 시작 위치 랜덤 기능을 사용하게 한다.
- “norandmaps” 커널 파라메터를 사용하는 경우에도 힙 시작 위치 랜덤 기능을 사용하지 않게 할 수 있다.
- 코드 라인 30~31에서 태스크에 설정된 힙 시작 주소 보다 낮은 힙 주소를 요청하는 경우 할당을 포기하고 out 레이블로 이동한다.
- 코드 라인 39~41에서 현재 태스크가 사용하는 데이터 크기가 현재 태스크에 설정된 data 영역 한계 용량을 초과하는 경우 할당을 포기하고 out 레이블로 이동한다.
- RLIMIT_DATA: 데이터(힙 사용량 + 데이터 섹션) 사이즈 limit
- 코드 라인 43~48에서 요청한 힙 주소의 페이지 단위 변화가 없는 경우 success 레이블로 이동한다.
- 코드 라인 54~71에서 요청한 힙 주소가 태스크에 설정한 기존 힙 주소 이하인 경우 힙을 그 줄어든 차이 언매핑하여 축소(shrink) 한다. 축소가 성공하면 success 레이블로 이동하고 그렇지 않은 경우 out 레이블로 이동한다.
mm/mmap.c -2/2-
/* Check against existing mmap mappings. */
next = find_vma(mm, oldbrk);
if (next && newbrk + PAGE_SIZE > vm_start_gap(next))
goto out;
/* Ok, looks good - let it rip. */
if (do_brk_flags(oldbrk, newbrk-oldbrk, 0, &uf) < 0)
goto out;
mm->brk = brk;
success:
populate = newbrk > oldbrk && (mm->def_flags & VM_LOCKED) != 0;
if (downgraded)
up_read(&mm->mmap_sem);
else
up_write(&mm->mmap_sem);
userfaultfd_unmap_complete(mm, &uf);
if (populate)
mm_populate(oldbrk, newbrk - oldbrk);
return brk;
out:
retval = origbrk;
up_write(&mm->mmap_sem);
return retval;
}
- 코드 라인 2~4에서 늘어날 힙 공간이 기존에 이미 매핑되어 있는 경우 할당을 포기하고 out 레이블로 이동한다.
- 코드 라인 7~8에서 기존 vm을 확장하여 반환하거나 새 vm을 구성하여 가져온다. 실패하는 경우 out 레이블로 이동한다.
- 코드 라인 11~19에서 success: 레이블이다. 늘어난 힙이 있으면서 mlocked 영역의 vma인 경우 해당 영역에 대한 유저 페이지를 모두 할당하여 매핑한다.
- 코드 라인 20에서 새 힙의 끝 주소를 반환한다.
- 코드 라인 22~25에서 out: 레이블이다. 기존 힙 끝 주소를 반환한다.
다음 그림은 do_brk() 함수가 호출될 때 힙이 확장되거나 줄어드는 모습을 보여준다.
check_data_rlimit()
include/linux/mm.h
static inline int check_data_rlimit(unsigned long rlim,
unsigned long new,
unsigned long start,
unsigned long end_data,
unsigned long start_data)
{
if (rlim < RLIM_INFINITY) {
if (((new - start) + (end_data - start_data)) > rlim)
return -ENOSPC;
}
return 0;
}
데이터 사용 크기가 rlim을 초과하는 경우 -ENOSPC 에러 값을 반환한다.
do_brk_flags()
mm/mmap.c
/*
* this is really a simplified "do_mmap". it only handles
* anonymous maps. eventually we may be able to do some
* brk-specific accounting here.
*/
static int do_brk_flags(unsigned long addr, unsigned long len, unsigned long flags, struct list_headd
*uf)
{
struct mm_struct *mm = current->mm;
struct vm_area_struct *vma, *prev;
struct rb_node **rb_link, *rb_parent;
pgoff_t pgoff = addr >> PAGE_SHIFT;
int error;
/* Until we need other flags, refuse anything except VM_EXEC. */
if ((flags & (~VM_EXEC)) != 0)
return -EINVAL;
flags |= VM_DATA_DEFAULT_FLAGS | VM_ACCOUNT | mm->def_flags;
error = get_unmapped_area(NULL, addr, len, 0, MAP_FIXED);
if (offset_in_page(error))
return error;
error = mlock_future_check(mm, mm->def_flags, len);
if (error)
return error;
/*
* Clear old maps. this also does some error checking for us
*/
while (find_vma_links(mm, addr, addr + len, &prev, &rb_link,
&rb_parent)) {
if (do_munmap(mm, addr, len, uf))
return -ENOMEM;
}
/* Check against address space limits *after* clearing old maps... */
if (!may_expand_vm(mm, flags, len >> PAGE_SHIFT))
return -ENOMEM;
if (mm->map_count > sysctl_max_map_count)
return -ENOMEM;
if (security_vm_enough_memory_mm(mm, len >> PAGE_SHIFT))
return -ENOMEM;
/* Can we just expand an old private anonymous mapping? */
vma = vma_merge(mm, prev, addr, addr + len, flags,
NULL, NULL, pgoff, NULL, NULL_VM_UFFD_CTX);
if (vma)
goto out;
/*
* create a vma struct for an anonymous mapping
*/
vma = vm_area_alloc(mm);
if (!vma) {
vm_unacct_memory(len >> PAGE_SHIFT);
return -ENOMEM;
}
vma_set_anonymous(vma);
vma->vm_start = addr;
vma->vm_end = addr + len;
vma->vm_pgoff = pgoff;
vma->vm_flags = flags;
vma->vm_page_prot = vm_get_page_prot(flags);
vma_link(mm, vma, prev, rb_link, rb_parent);
out:
perf_event_mmap(vma);
mm->total_vm += len >> PAGE_SHIFT;
mm->data_vm += len >> PAGE_SHIFT;
if (flags & VM_LOCKED)
mm->locked_vm += (len >> PAGE_SHIFT);
vma->vm_flags |= VM_SOFTDIRTY;
return 0;
}
현재 태스크 유저 영역에서 요청한 가상 주소와 길이만큼의 영역을 고정 매핑한다. 성공 시 0을 반환한다.
- 코드 라인 7에서 가상 주소에 대한 페이지 번호를 pgoff에 담는다.
- 캐시 aliasing을 사용하는 시스템에서 시작 주소가 적절한지 비교하기 위해 사용된다.
- 코드 라인 11~12에서 VM_EXEC를 제외한 모든 플래그의 사용을 허용하지 않는다.
- 코드 라인 13에서 코드 라인 19에서 VM_DATA_DEFAULT_FLAGS와 VM_ACCOUNT 및 현재 태스크의 def_flags를 담는다.
- VM_DATA_DEFAULT_FLAGS:
- VM_EXEC(옵션) | VM_READ | VM_WRITE | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC
- 코드 라인 15~17에서 현재 태스크 유저 영역의 요청 가상 주소부터 길이 len만큼의 빈 공간이 있어 고정 매핑시킬 수 있는지 여부를 알아온다. 만일 매핑할 공간이 없으면 error를 반환한다.
- 코드 라인 19~21에서 현재 태스크에서 VM_LOCKED 플래그를 사용한 페이지들의 수가 최대 locked 페이지 수 제한을 초과하는 경우 -EAGAIN 에러를 반환한다.
- 코드 라인 26~30에서 vma들에서 요청 가상 주소 영역과 겹치는 경우 언맵을 수행한다.
- 코드 라인 33~34에서 현재 태스크의 전체 vm 페이지 수가 주소 공간 제한(RLIMIT_AS)을 초과하는 경우 -ENOMEM 에러를 반환한다.
- 코드 라인 36~37에서 현재 태스크의 vma 수가 최대 매핑 카운트 수를 초과하는 경우 -ENOMEM을 반환한다.
- sysctl_max_map_count
- 디폴트로 65530이며 이 값은 “/proc/sys/vm/max_map_count” 를 통해 변경할 수 있다.
- 코드 라인 39~40에서 LSM(Linux Security Module)을 통해 새로운 가상 매핑의 할당이 충분한지 여부를 체크한다.
- 코드 라인 43~46에서 기존 vma가 private anonymous 매핑을 사용하는 경우 merge하여 확장할 수 있는지 확인하고 가능하면 out 레이블로 이동한다.
- 코드 라인 51~55에서 vma 구조체용 메모리를 할당하고 실패시 이미 증가시킨 vm commit 페이지 수를 다시 원상복귀 시키고 -ENOMEM 에러를 반환한다.
- 코드 라인 57~63에서 vma 정보를 구성하고 추가한다.
- vm_page_prot에 들어가는 매핑 속성은 메모리 디스크립터에 특별히 추가된 속성(mm->def_flags)이 없어도 기본적으로 __PAGE_COPY이다.
- 코드 라인 64~67에서 out 레이블의 시작 위치이며 메모리 디스크립터에 전체 사용 vm 페이지 수를 갱신한다.
- 코드 라인 68~69에서 VM_LOCKED 플래그를 사요하는 경우 메모리 디스크립터의 locked_vm 페이지 카운터를 갱신한다.
- 코드 라인 70에서 vma의 플래그에 VM_SOFTDIRTY를 추가한다.
- 코드 라인 71에서 성공 0을 반환한다.
다음 그림은 brk() 요청에 대하여 기존 vma를 사용하여 확장하는 모습을 보여준다.
vm 플래그 -> 페이지 매핑 속성
vm_get_page_prot()
mm/mmap.c
pgprot_t vm_get_page_prot(unsigned long vm_flags)
{
return __pgprot(pgprot_val(protection_map[vm_flags &
(VM_READ|VM_WRITE|VM_EXEC|VM_SHARED)]) |
pgprot_val(arch_vm_get_page_prot(vm_flags)));
}
EXPORT_SYMBOL(vm_get_page_prot);
vm 플래그들 중 read, write, exec, shared 플래그 값의 사용 우무로 필요한 페이지 매핑 속성 값들을 알아온다.
전역 protection_map[] 배열
mm/mmap.c
/* description of effects of mapping type and prot in current implementation.
* this is due to the limited x86 page protection hardware. The expected
* behavior is in parens:
*
* map_type prot
* PROT_NONE PROT_READ PROT_WRITE PROT_EXEC
* MAP_SHARED r: (no) no r: (yes) yes r: (no) yes r: (no) yes
* w: (no) no w: (no) no w: (yes) yes w: (no) no
* x: (no) no x: (no) yes x: (no) yes x: (yes) yes
*
* MAP_PRIVATE r: (no) no r: (yes) yes r: (no) yes r: (no) yes
* w: (no) no w: (no) no w: (copy) copy w: (no) no
* x: (no) no x: (no) yes x: (no) yes x: (yes) yes
*
*/
pgprot_t protection_map[16] __ro_after_init = {
__P000, __P001, __P010, __P011, __P100, __P101, __P110, __P111,
__S000, __S001, __S010, __S011, __S100, __S101, __S110, __S111
};
4개의 플래그 비트로 16개의 배열이 작성된다.
16개의 페이지 매핑 속성 – ARM32
arch/arm/include/asm/pgtable.h
/*
* The table below defines the page protection levels that we insert into our
* Linux page table version. These get translated into the best that the
* architecture can perform. Note that on most ARM hardware:
* 1) We cannot do execute protection
* 2) If we could do execute protection, then read is implied
* 3) write implies read permissions
*/
#define __P000 __PAGE_NONE
#define __P001 __PAGE_READONLY
#define __P010 __PAGE_COPY
#define __P011 __PAGE_COPY
#define __P100 __PAGE_READONLY_EXEC
#define __P101 __PAGE_READONLY_EXEC
#define __P110 __PAGE_COPY_EXEC
#define __P111 __PAGE_COPY_EXEC
#define __S000 __PAGE_NONE
#define __S001 __PAGE_READONLY
#define __S010 __PAGE_SHARED
#define __S011 __PAGE_SHARED
#define __S100 __PAGE_READONLY_EXEC
#define __S101 __PAGE_READONLY_EXEC
#define __S110 __PAGE_SHARED_EXEC
#define __S111 __PAGE_SHARED_EXEC
read, write, exec, shared 플래그 비트로 조합한 16개의 매크로 상수 값
arch/arm/include/asm/pgtable.h
#define __PAGE_NONE __pgprot(_L_PTE_DEFAULT | L_PTE_RDONLY | L_PTE_XN | L_PTE_NONE)
#define __PAGE_SHARED __pgprot(_L_PTE_DEFAULT | L_PTE_USER | L_PTE_XN)
#define __PAGE_SHARED_EXEC __pgprot(_L_PTE_DEFAULT | L_PTE_USER)
#define __PAGE_COPY __pgprot(_L_PTE_DEFAULT | L_PTE_USER | L_PTE_RDONLY | L_PTE_XN)
#define __PAGE_COPY_EXEC __pgprot(_L_PTE_DEFAULT | L_PTE_USER | L_PTE_RDONLY)
#define __PAGE_READONLY __pgprot(_L_PTE_DEFAULT | L_PTE_USER | L_PTE_RDONLY | L_PTE_XN)
#define __PAGE_READONLY_EXEC __pgprot(_L_PTE_DEFAULT | L_PTE_USER | L_PTE_RDONLY)
- __PAGE_NONE
- NUMA 시스템에서 해당 페이지를 읽을 때 accesss 권한 실패로 인해 abort exception이 발생되어 fault된 후 해당 페이지를 사용하는 태스크의 migration을 고려하는 Automatic NUMA balancing을 위해 사용된다.
- __PAGE_COPY
- L_PTE_PRESENT: 매핑됨
- L_PTE_YOUNG: 페이지에 접근 가능
- L_PTE_USER: 유저 허용
- L_PTE_RDONLY: 읽기 전용
- L_PTE_XN: 실행 금지(Excute Never)
16개의 페이지 매핑 속성 – ARM64
arch/arm64/include/asm/pgtable-prot.h
#define __P000 PAGE_NONE
#define __P001 PAGE_READONLY
#define __P010 PAGE_READONLY
#define __P011 PAGE_READONLY
#define __P100 PAGE_EXECONLY
#define __P101 PAGE_READONLY_EXEC
#define __P110 PAGE_READONLY_EXEC
#define __P111 PAGE_READONLY_EXEC
#define __S000 PAGE_NONE
#define __S001 PAGE_READONLY
#define __S010 PAGE_SHARED
#define __S011 PAGE_SHARED
#define __S100 PAGE_EXECONLY
#define __S101 PAGE_READONLY_EXEC
#define __S110 PAGE_SHARED_EXEC
#define __S111 PAGE_SHARED_EXEC
arch/arm64/include/asm/pgtable-prot.h
#define PAGE_NONE __pgprot(((_PAGE_DEFAULT) & ~PTE_VALID) | PTE_PROT_NONE | PTE_RDONLYY
| PTE_NG | PTE_PXN | PTE_UXN)
#define PAGE_SHARED __pgprot(_PAGE_DEFAULT | PTE_USER | PTE_NG | PTE_PXN | PTE_UXN | PTEE
_WRITE)
#define PAGE_SHARED_EXEC __pgprot(_PAGE_DEFAULT | PTE_USER | PTE_NG | PTE_PXN | PTE_WRITE)
#define PAGE_READONLY __pgprot(_PAGE_DEFAULT | PTE_USER | PTE_RDONLY | PTE_NG | PTE_PXN |
PTE_UXN)
#define PAGE_READONLY_EXEC __pgprot(_PAGE_DEFAULT | PTE_USER | PTE_RDONLY | PTE_NG | PTE_PXN)
#define PAGE_EXECONLY __pgprot(_PAGE_DEFAULT | PTE_RDONLY | PTE_NG | PTE_PXN)
- _PAGE_DEFAULT
- PTE_ATTRINDX(MT_NORMAL) | PTE_TYPE_PAGE | PTE_AF | PTE_SHARED
매핑되지 않은 주소 영역 찾기
get_unmapped_area()
mm/mmap.c
unsigned long
get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
unsigned long pgoff, unsigned long flags)
{
unsigned long (*get_area)(struct file *, unsigned long,
unsigned long, unsigned long, unsigned long);
unsigned long error = arch_mmap_check(addr, len, flags);
if (error)
return error;
/* Careful about overflows.. */
if (len > TASK_SIZE)
return -ENOMEM;
get_area = current->mm->get_unmapped_area;
if (file) {
if (file->f_op->get_unmapped_area)
get_area = file->f_op->get_unmapped_area;
} else if (flags & MAP_SHARED) {
/*
* mmap_region() will call shmem_zero_setup() to create a file,
* so use shmem's get_unmapped_area in case it can be huge.
* do_mmap_pgoff() will clear pgoff, so match alignment.
*/
pgoff = 0;
get_area = shmem_get_unmapped_area;
}
addr = get_area(file, addr, len, pgoff, flags);
if (IS_ERR_VALUE(addr))
return addr;
if (addr > TASK_SIZE - len)
return -ENOMEM;
if (offset_in_page(addr))
return -EINVAL;
error = security_mmap_addr(addr);
return error ? error : addr;
}
EXPORT_SYMBOL(get_unmapped_area);
현재 태스크 유저 영역의 mmap 매핑 공간에서 검색하여 요청 길이가 들어갈 수 있는 매핑되지 않은 빈 영역의 가상 시작 주소를 알아온다.
- 코드 라인 8~10에서 요청한 유저 공간이 아키텍처가 지원하지 않는 매핑 공간인 경우 에러를 반환한다.
- 코드 라인 13~14에서 요청 할당 길이가 유저 공간 크기보다 큰 경우 -ENOMEM 에러를 반환한다.
- TASK_SIZE: 유저 공간의 크기
- 예) rpi2: 2G – 16M (arm에서는 커널 공간과 모듈(16M) 공간을 제외한 크기)
- 코드 라인 16~32에서 언맵된 영역을 알아온다.
- file 매핑인 경우 file 디스크립터로부터 언맵된 영역을 알아오는 핸들러 함수를 사용한다.
- 참고로 do_brk()는 file 매핑을 사용하지 않고 anon 매핑을 위해 file 인수에 null을 대입하여 호출한다.
- shared 영역에 대한 핸들러 함수는 shmem_get_unmapped_area() 함수를 사용한다.
- 코드 라인 34~35에서 알아온 가상 주소를 유저 공간에 배치할 수 없는 경우 -ENOMEM 에러를 반환한다.
- 코드 라인 36~37에서 알아온 가상 주소가 0페이지인 경우 -EINVAL 에러를 반환한다.
- 코드 라인 39~30에서 보안을 위해 사용되는 selinux가 사용될 때, 해당 가상 주소가 허가된 주소인 경우 그 주소를 반환하고 그렇지 않은 경우 에러를 반환한다.
arch_mmap_check()
arch/arm/include/uapi/asm/mman.h
#define arch_mmap_check(addr, len, flags) \
(((flags) & MAP_FIXED && (addr) < FIRST_USER_ADDRESS) ? -EINVAL : 0)
요청한 가상주소로 고정 매핑을 요구하는 경우 그 가상 주소가 시작 유저 공간 주소 이하인 경우 -EINVAL을 반환한다.
- FIRST_USER_ADDRESS: (PAGE_SIZE * 2)
- arm에서 로우 벡터를 사용하는 경우 하위 2개 페이지는 사용자가 사용할 수 없는 공간이다.
- ARM64 및 x86의 경우 항상 성공 0을 반환한다.
arch_get_unmapped_area() – ARM32
arch/arm/mm/mmap.c
/*
* We need to ensure that shared mappings are correctly aligned to
* avoid aliasing issues with VIPT caches. We need to ensure that
* a specific page of an object is always mapped at a multiple of
* SHMLBA bytes.
*
* We unconditionally provide this function for all cases, however
* in the VIVT case, we optimise out the alignment rules.
*/
unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
unsigned long len, unsigned long pgoff, unsigned long flags)
{
struct mm_struct *mm = current->mm;
struct vm_area_struct *vma;
int do_align = 0;
int aliasing = cache_is_vipt_aliasing();
struct vm_unmapped_area_info info;
/*
* We only need to do colour alignment if either the I or D
* caches alias.
*/
if (aliasing)
do_align = filp || (flags & MAP_SHARED);
/*
* We enforce the MAP_FIXED case.
*/
if (flags & MAP_FIXED) {
if (aliasing && flags & MAP_SHARED &&
(addr - (pgoff << PAGE_SHIFT)) & (SHMLBA - 1))
return -EINVAL;
return addr;
}
if (len > TASK_SIZE)
return -ENOMEM;
if (addr) {
if (do_align)
addr = COLOUR_ALIGN(addr, pgoff);
else
addr = PAGE_ALIGN(addr);
vma = find_vma(mm, addr);
if (TASK_SIZE - len >= addr &&
(!vma || addr + len <= vma->vm_start))
return addr;
}
info.flags = 0;
info.length = len;
info.low_limit = mm->mmap_base;
info.high_limit = TASK_SIZE;
info.align_mask = do_align ? (PAGE_MASK & (SHMLBA - 1)) : 0;
info.align_offset = pgoff << PAGE_SHIFT;
return vm_unmapped_area(&info);
}
arm 아키텍처용으로 구현된 함수로 현재 태스크 유저 영역의 mmap 매핑 공간에서 아래에서 위로 검색하여 요청 길이가 들어갈 수 있는 매핑되지 않은 빈 영역의 가상 시작 주소를 알아온다.
- 코드 라인 8에서 현재 아키텍처의 데이터 캐시가 vipt aliasing을 사용하는지 여부를 알아온다.
- rpi2: aliasing을 사용하지 않는다.
- 코드 라인 15~16에서 aliasing이 사용되는 경우 do_align 값에 flip(파일 구조체 포인터) 값 + MAP_SHARED(1) 플래그를 대입하여 align이 필요한지 여부를 구한다.
- 코드 라인 21~26에서 vm 고정 매핑을 요청한 경우 요청한 가상 주소를 그대로 사용해야 하므로 가상 주소를 변경하지 않고 함수를 빠져나간다. 단 aliasing 및 공유맵을 요청받은 경우 pgoff 페이지 만큼을 감소시킨 가상 주소가 aliasing에 필요한 SHMLBA 사이즈 단위로 정렬되지 않는 경우 -EINVAL을 반환한다.
- SHMLBA: armv7 이전 아키텍처에서 aliasing에 대한 보정때문에 매핑 페이지를 공유해야하는 경우 태스크들 간에 4개 페이지(16K) 이내의 가상 주소 매핑을 사용하지 못하게 한다.
- 코드 라인 28~29에서 길이가 유저 공간 크기를 초과하는 경우 -ENOMEM 에러를 반환한다.
- 코드 라인 31~35에서 가상 주소가 지정된 경우 페이지 단위로 정렬하되 do_align이 설정되어 있으면 가상 주소를 aliasing에 맞게 정렬시킨다.
- 코드 라인 37에서 현재 태스크에 등록된 vma 정보에서 vma를 찾아온다.
- 코드 라인 38~40에서 조절된 가상 주소가 유저 공간에 배치 가능하고 vma 영역 이하인 경우 함수를 빠져나간다.
- 코드 라인 43~49에서 다음과 같이 vm 언맵된 영역 정보를 구성한 후 언맵된 영역을 찾아 반환한다.
- low_limit에는 매핑 영역 하한 주소를 대입한다.
- high_limit에는 user 공간의 상한 주소를 대입한다.
- align_mask는 aliasing이 필요한 arm 아키텍처에 대해 필요한 크기-1 페이지(3 페이지=0x3000)를 대입하여 매핑할 영역 뒷부분을 사용하지 못하게 하는 용도로 배정한다.
- align_offset는 페이지에서 읽어올 offset 페이지 번호를 대입한다.
아래 두 개의 그림은 fixed 매핑 여부에 따라 매핑 공간의 시작 주소와 크기가 캐시 aliasing에 의해 변경될 수 있음을 보여준다.
COLOUR_ALIGN()
mm/mmap.c
#define COLOUR_ALIGN(addr,pgoff) \
((((addr)+SHMLBA-1)&~(SHMLBA-1)) + \
(((pgoff)<<PAGE_SHIFT) & (SHMLBA-1)))
데이터 캐시가 vipt aliasing을 사용하는 경우 페이지 컬러링에 맞추어 요청 가상 주소를 정렬한다.
- 예) SHMLBA=16K , addr=0x1234_6000, pgoff=7
- 가상 주소를 16K 단위로 정렬 + pgoff 페이지를 16K 페이지단위로 나눈 나머지
- 0x1234_8000 + 0x3000 = 0x1234_b000
arch_get_unmapped_area() – Generic (x86, ARM64, …)
mm/mmap.c
/* Get an address range which is currently unmapped.
* For shmat() with addr=0.
*
* Ugly calling convention alert:
* Return value with the low bits set means error value,
* ie
* if (ret & ~PAGE_MASK)
* error = ret;
*
* This function "knows" that -ENOMEM has the bits set.
*/
#ifndef HAVE_ARCH_UNMAPPED_AREA
unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
unsigned long len, unsigned long pgoff, unsigned long flags)
{
struct mm_struct *mm = current->mm;
struct vm_area_struct *vma, *prev;
struct vm_unmapped_area_info info;
const unsigned long mmap_end = arch_get_mmap_end(addr);
if (len > mmap_end - mmap_min_addr)
return -ENOMEM;
if (flags & MAP_FIXED)
return addr;
if (addr) {
addr = PAGE_ALIGN(addr);
vma = find_vma_prev(mm, addr, &prev);
if (mmap_end - len >= addr && addr >= mmap_min_addr &&
(!vma || addr + len <= vm_start_gap(vma)) &&
(!prev || addr >= vm_end_gap(prev)))
return addr;
}
info.flags = 0;
info.length = len;
info.low_limit = mm->mmap_base;
info.high_limit = mmap_end;
info.align_mask = 0;
return vm_unmapped_area(&info);
}
#endif
generic(x86, ARM64 등이 포함됨)으로 구현된 함수로 현재 태스크 유저 영역의 mmap 매핑 공간에서 아래에서 위로 검색하여 요청 길이가 들어갈 수 있는 매핑되지 않은 빈 영역의 가상 시작 주소를 알아온다.
- 코드 라인 11~12에서 아키텍처가 지원하는 최대 크기를 넘어서면 -ENOMEM 에러를 반환한다.
- 코드 라인 14~15에서 MAP_FIXED 플래그를 사용한 경우 주소 변환 없이 @addr을 그대로 반환한다.
- 코드 라인 17~24에서 가상 주소 @addr가 지정된 경우 페이지 단위로 정렬하고, 현재 태스크에 등록된 vma 정보에서 vma를 찾아온다. 만일 가상 주소가 유저 공간에 배치 가능하고 vma 영역 이하인 경우 함수를 빠져나간다.
- 코드 라인 26~31에서 다음 정보로 언맵된 영역을 찾아 그 가상 주소를 반환한다.
- low_limit에는 매핑 영역 하한 주소를 대입한다.
- high_limit에는 user 공간의 상한 주소를 대입한다.
arch_get_mmap_base() & arch_get_mmap_end() – ARM64
arch/arm64/include/asm/processor.h
#ifndef CONFIG_ARM64_FORCE_52BIT
#define arch_get_mmap_end(addr) ((addr > DEFAULT_MAP_WINDOW) ? TASK_SIZE :\
DEFAULT_MAP_WINDOW)
#define arch_get_mmap_base(addr, base) ((addr > DEFAULT_MAP_WINDOW) ? \
base + TASK_SIZE - DEFAULT_MAP_WINDOW :\
base)
#endif /* CONFIG_ARM64_FORCE_52BIT */
vm_unmapped_area()
include/linux/mm.h
/*
* Search for an unmapped address range.
*
* We are looking for a range that:
* - does not intersect with any VMA;
* - is contained within the [low_limit, high_limit) interval;
* - is at least the desired size.
* - satisfies (begin_addr & align_mask) == (align_offset & align_mask)
*/
static inline unsigned long
vm_unmapped_area(struct vm_unmapped_area_info *info)
{
if (!(info->flags & VM_UNMAPPED_AREA_TOPDOWN))
return unmapped_area(info);
else
return unmapped_area_topdown(info);
}
언맵된 영역의 가상 주소를 알아온다.
- VM_UNMAPPED_AREA_TOPDOWN 플래그 사용 여부에 따라 검색 방향이 결정된다.
아래에서 위로 주소 영역 찾기
unmapped_area()
mm/mmap.c -1/2-
unsigned long unmapped_area(struct vm_unmapped_area_info *info)
{
/*
* We implement the search by looking for an rbtree node that
* immediately follows a suitable gap. That is,
* - gap_start = vma->vm_prev->vm_end <= info->high_limit - length;
* - gap_end = vma->vm_start >= info->low_limit + length;
* - gap_end - gap_start >= length
*/
struct mm_struct *mm = current->mm;
struct vm_area_struct *vma;
unsigned long length, low_limit, high_limit, gap_start, gap_end;
/* Adjust search length to account for worst case alignment overhead */
length = info->length + info->align_mask;
if (length < info->length)
return -ENOMEM;
/* Adjust search limits by the desired length */
if (info->high_limit < length)
return -ENOMEM;
high_limit = info->high_limit - length;
if (info->low_limit > high_limit)
return -ENOMEM;
low_limit = info->low_limit + length;
/* Check if rbtree root looks promising */
if (RB_EMPTY_ROOT(&mm->mm_rb))
goto check_highest;
vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
if (vma->rb_subtree_gap < length)
goto check_highest;
while (true) {
/* Visit left subtree if it looks promising */
gap_end = vm_start_gap(vma);
if (gap_end >= low_limit && vma->vm_rb.rb_left) {
struct vm_area_struct *left =
rb_entry(vma->vm_rb.rb_left,
struct vm_area_struct, vm_rb);
if (left->rb_subtree_gap >= length) {
vma = left;
continue;
}
}
augmented rbtrees를 사용하여 구현된 함수로 유저 공간의 요청 범위에서 아래에서 위로 검색하여 vma 영역들 사이의 매핑되지 않은 빈(gap) 영역들 중 요청 길이가 들어갈 수 있는 빈(gap) 영역의 가상 시작 주소를 알아온다.
- 코드 라인 16~18에서 align_mask를 추가한 길이를 구하고, 길이가 시스템 주소 영역을 초과하는 경우 -ENOMEM 에러를 반환한다.
- 코드 라인 21~23에서 high_limit을 산출한다. 범위를 벗어나는 경우 -ENOMEM 에러를 반환한다.
- 기존 high_limit 에서 길이만큼 뺸 값
- 코드 라인 25~27에서 low_limit을 산출한다. 범위를 벗어나는 경우 -ENOMEM 에러를 반환한다.
- 기존 low_limit 에서 길이만큼 추가한 값
- 코드 라인 30~31에서 메모리 디스크립터의 rb 트리가 비어있는 경우 check_highest 레이블로 이동한다.
- 코드 라인 32~34에서 메모리 디스크립터의 루트 노드에서 vma를 가져온다. 만일 루트 노드의 rb_subtree_gap이 길이보다 작은 경우 루트 노드 이하의 노드들에는 빈 공간이 없으므로 최상위 공간을 체크하기 위해 check_highest 레이블로 이동한다.
- 루트 노드의 rb_subtree_gap이 length보다 작은 경우 즉, 각 vma 간 gap이 length보다 작아 그 사이에 추가할 수 없으므로 최상위 영역을 조사한다.
- 코드 라인 36~47에서 현재 태스크의 가상 메모리 영역 vma 들을 대상으로 루프를 돌며 rb 트리에서 좌측 노드 방향으로 길이 만큼의 gap 공간이 발견되는 노드를 찾는다.
mm/mmap.c -2/2-
gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
check_current:
/* Check if current node has a suitable gap */
if (gap_start > high_limit)
return -ENOMEM;
if (gap_end >= low_limit &&
gap_end > gap_start && gap_end - gap_start >= length)
goto found;
/* Visit right subtree if it looks promising */
if (vma->vm_rb.rb_right) {
struct vm_area_struct *right =
rb_entry(vma->vm_rb.rb_right,
struct vm_area_struct, vm_rb);
if (right->rb_subtree_gap >= length) {
vma = right;
continue;
}
}
/* Go back up the rbtree to find next candidate node */
while (true) {
struct rb_node *prev = &vma->vm_rb;
if (!rb_parent(prev))
goto check_highest;
vma = rb_entry(rb_parent(prev),
struct vm_area_struct, vm_rb);
if (prev == vma->vm_rb.rb_left) {
gap_start = vm_end_gap(vma->vm_prev);
gap_end = vm_start_gap(vma);
goto check_current;
}
}
}
check_highest:
/* Check highest gap, which does not precede any rbtree node */
gap_start = mm->highest_vm_end;
gap_end = ULONG_MAX; /* Only for VM_BUG_ON below */
if (gap_start > high_limit)
return -ENOMEM;
found:
/* We found a suitable gap. Clip it with the original low_limit. */
if (gap_start < info->low_limit)
gap_start = info->low_limit;
/* Adjust gap address to the desired alignment */
gap_start += (info->align_offset - gap_start) & info->align_mask;
VM_BUG_ON(gap_start + info->length > info->high_limit);
VM_BUG_ON(gap_start + info->length > gap_end);
return gap_start;
}
- 코드 라인 1에서 gap 시작 주소를 산출한다.
- 코드 라인 2~5에서 check_current: 레이블이다. gap 시작 주소가 high_limit을 벗어나는 경우 -ENOMEM 에러를 반환한다.
- 코드 라인 6~8에서 gap_end가 low_limit 이상이면서 gap 영역이 길이 보다 큰 경우 found 레이블로 이동한다.
- 코드 라인 11~19에서 이 번에는 반대로 노드의 하위 우측 노드가 있고 그 노드의 gap 영역이 길이 보다 큰 경우 그 우측 노드를 vma 영역에 대입하고 루프를 계속 진행한다.
- 코드 라인 22~33에서 하위에 적당한 gap 영역이 없는 경우 다시 상위 노드로 올라가는데 좌측 노드에서 상위 노드로 올라간 경우라면 gap 시작과 끝을 갱신하고 check_current 레이블로 이동한다.
- 코드 라인 36~41에서 check_highest: 레이블이다. 이 곳에서는 rb 트리의 빈 영역에 필요한 공간이 없어 그 상위의 빈자리를 찾는데 이 곳에서도 적절한 공간이 확보되지 않으면 -ENOMEM 에러를 반환한다.
- 코드 라인 43~46에서 found: 레이블이다. 찾은 gap의 시작 위치를 최소한 info->low_limit으로 조절한다.
- 코드 라인 49~53에서 gap의 시작 위치는 조절된 gap offset 만큼을 추가한 후 info->align_mask로 절삭하여 조절하고 반환한다.
- file 및 캐시 aliasing으로 인해 찾은 언매핑 영역(gap)의 시작위치가 조절될 수 있다.
vm_start_gap()
include/linux/mm.h
static inline unsigned long vm_start_gap(struct vm_area_struct *vma)
{
unsigned long vm_start = vma->vm_start;
if (vma->vm_flags & VM_GROWSDOWN) {
vm_start -= stack_guard_gap;
if (vm_start > vma->vm_start)
vm_start = 0;
}
return vm_start;
}
스택 가드 갭이 적용된 vma 시작 주소를 반환한다.
vm_end_gap()
include/linux/mm.h
static inline unsigned long vm_end_gap(struct vm_area_struct *vma)
{
unsigned long vm_end = vma->vm_end;
if (vma->vm_flags & VM_GROWSUP) {
vm_end += stack_guard_gap;
if (vm_end < vma->vm_end)
vm_end = -PAGE_SIZE;
}
return vm_end;
}
스택 가드 갭이 적용된 vma 끝 주소를 반환한다.
Augmented rbtrees
레드 블랙 트리를 확장하여 augmented rbtree를 사용할 수 있는데 노드들에 대해 추가 정보를 저장할 수 있다. 노드에 대해 전파(propagation), 복사(copy), 회전(rotation)에 대한 콜백 함수를 사용자가 작성하여 등록하면 노드에 대해 변경이 일어날 때 마다 호출되어 추가적인 정보의 관리가 가능하게 만들어졌다. 커널에서도 vma 영역을 rbtree로 관리하는데 augmented rbtrees 방식이 도입되어 매핑되지 않은 빈 영역을 찾을 때 사용하기 위해 서브 트리들이 관리하는 gap 영역에 대한 추가 정보를 관리한다.
아래 그림은 각 노드가 하위 노드들에서 가장 큰 gap 정보를 선택하여 관리하고 있는 모습을 보여준다.
최대 VM_LOCKED 페이지 수 제한
mlock_future_check()
mm/mmap.c
static inline int mlock_future_check(struct mm_struct *mm,
unsigned long flags,
unsigned long len)
{
unsigned long locked, lock_limit;
/* mlock MCL_FUTURE? */
if (flags & VM_LOCKED) {
locked = len >> PAGE_SHIFT;
locked += mm->locked_vm;
lock_limit = rlimit(RLIMIT_MEMLOCK);
lock_limit >>= PAGE_SHIFT;
if (locked > lock_limit && !capable(CAP_IPC_LOCK))
return -EAGAIN;
}
return 0;
}
현재 태스크에서 VM_LOCKED 플래그를 사용한 페이지들의 수가 최대 locked 페이지 수 제한을 초과하는 경우 -EAGAIN 에러를 반환한다. 그 외 성공리에 0을 반환한다.
- VM_LOCKED된 매핑 영역은 페이지 회수(compaction 및 reclaim) 시스템에서 skip 한다.
참고
