한 page의 mapping을 지웠다고 그 PTE table 전체를 free할 수는 없습니다. 같은 table의 다른 entry가 이웃 VMA를 mapping할 수 있기 때문입니다. data page 제거와 table page의 마지막 사용 종료에는 서로 다른 범위 검사가 필요합니다.
floor와 ceiling이 이웃을 보호합니다
free_pgtables()는 제거 대상 VMA의 rmap 연결을 정리하고 table 해제를 진행합니다. caller가 제거 대상만 분리해 넘겼다는 전제가 중요합니다. 전체 주소 공간의 다음 VMA까지 무작정 따라가며 unlink하는 함수로 사용해서는 안 됩니다.
PTE table 한 page는 x86-64의 4 KiB base-page 구성에서 2 MiB VA를 표현합니다. table을 free하려면 이 granularity에서 이웃이 여전히 사용하는 부분이 없는지 알아야 합니다. floor·ceiling은 그 경계를 제공하며 인접 제거 VMA를 묶으면 같은 table 범위를 효율적으로 처리할 수 있습니다.
주소 공간의 양 끝과 overflow
range 계산에서는 주소 0을 실제 최저 주소와 최상단 sentinel의 표현에 사용할 수 있어 end·ceiling 비교에 -1 변환이 필요합니다. 정렬한 ceiling이 너무 낮거나 범위가 table 한 단위도 확실히 포함하지 못하면 해제를 건너뜁니다. floor를 넘기려고 PMD_SIZE를 더할 때 wrap하면 종료해야 합니다.
이 계산은 단순한 defensive programming이 아닙니다. table 하나를 잘못 free하면 제거하지 않은 VMA의 mapping도 접근 불가능해집니다. empty PTE의 개수만 세어서는 caller가 가진 범위 보장과 경쟁 조건을 대신할 수 없습니다.
하위 table을 없앤 level에서 상위 entry를 지웁니다
walk는 하위 table을 처리한 뒤 그것을 가리키는 상위 entry를 clear합니다. P4D table 해제가 PGD entry를, PUD table 해제가 P4D entry를 정리하는 식입니다. folded level은 실제 table allocation이 없으므로 architecture helper가 그 차이를 감춥니다.
PTE table을 제거할 수 있는 범위를 이미 확인했다면 PMD entry를 지우고 pte_free_tlb() 계열에 table을 넘깁니다. page-table destructor와 관련 statistics 정리는 data folio free와 다릅니다. table metadata와 allocation accounting을 함께 반환해야 합니다.
hardware walker 외에 software reader도 있습니다
table page는 CPU의 hardware walk만 읽지 않습니다. fast GUP 같은 lockless software walker도 접근할 수 있습니다. data translation을 invalidate했다는 사실만으로 이 reader가 모두 끝났다고 판단할 수 없습니다. configuration에 따라 RCU table free와 batch protocol이 더해집니다.
따라서 pte_unmap()이 어떤 x86 context에서 단순해 보이더라도 API의 mapping·RCU 계약을 버릴 근거가 되지는 않습니다. 다른 architecture나 page-table lifetime 변경에서 그 가정이 깨질 수 있습니다. 최종 data reference release와 table page 재사용이 서로 다른 barrier를 기다릴 수 있다는 점이 핵심입니다.
먼저 rmap에서 숨기고 table을 제거합니다
다음 v6.0의 전체 함수는 free_pgtables()가 detached VMA chain을 순회하는 모습과 file interval tree에서 제거하는 과정을 이어 보여 줍니다. File VMA의 writable-mapping accounting과 cache 관련 hook도 생략하지 않았습니다. unlink가 file contents를 지우거나 backing inode의 마지막 reference를 모두 해제한다는 의미는 아닙니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/memory.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* demand-loading started 01.12.91 - seems it is high on the list of
* things wanted, and it should be easy to implement. - Linus
*/
/*
* Ok, demand-loading was easy, shared pages a little bit tricker. Shared
* pages started 02.12.91, seems to work. - Linus.
*
* Tested sharing by executing about 30 /bin/sh: under the old kernel it
* would have taken more than the 6M I have free, but it worked well as
* far as I could see.
*
* Also corrected some "invalidate()"s - I wasn't doing enough of them.
*/
/*
* Real VM (paging to/from disk) started 18.12.91. Much more work and
* thought has to go into this. Oh, well..
* 19.12.91 - works, somewhat. Sometimes I get faults, don't know why.
* Found it. Everything seems to work now.
* 20.12.91 - Ok, making the swap-device changeable like the root.
*/
/*
* 05.04.94 - Multi-page memory management added for v1.1.
* Idea by Alex Bligh (alex@cconcepts.co.uk)
*
* 16.07.99 - Support of BIGMEM added by Gerhard Wichert, Siemens AG
* (Gerhard.Wichert@pdb.siemens.de)
*
* Aug/Sep 2004 Changed to four level page tables (Andi Kleen)
*/
/* Upstream Linux v6.0: mm/memory.c:405-438
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
unsigned long floor, unsigned long ceiling)
{
while (vma) {
struct vm_area_struct *next = vma->vm_next;
unsigned long addr = vma->vm_start;
/*
* Hide vma from rmap and truncate_pagecache before freeing
* pgtables
*/
unlink_anon_vmas(vma);
unlink_file_vma(vma);
if (is_vm_hugetlb_page(vma)) {
hugetlb_free_pgd_range(tlb, addr, vma->vm_end,
floor, next ? next->vm_start : ceiling);
} else {
/*
* Optimization: gather nearby vmas into one call down
*/
while (next && next->vm_start <= vma->vm_end + PMD_SIZE
&& !is_vm_hugetlb_page(next)) {
vma = next;
next = vma->vm_next;
unlink_anon_vmas(vma);
unlink_file_vma(vma);
}
free_pgd_range(tlb, addr, vma->vm_end,
floor, next ? next->vm_start : ceiling);
}
vma = next;
}
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* mm/mmap.c
*
* Written by obz.
*
* Address space accounting code <alan@lxorguk.ukuu.org.uk>
*/
/* Upstream Linux v6.0: mm/mmap.c:122-132
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
void unlink_file_vma(struct vm_area_struct *vma)
{
struct file *file = vma->vm_file;
if (file) {
struct address_space *mapping = file->f_mapping;
i_mmap_lock_write(mapping);
__remove_shared_vm_struct(vma, file, mapping);
i_mmap_unlock_write(mapping);
}
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* mm/mmap.c
*
* Written by obz.
*
* Address space accounting code <alan@lxorguk.ukuu.org.uk>
*/
/* Upstream Linux v6.0: mm/mmap.c:107-116
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
static void __remove_shared_vm_struct(struct vm_area_struct *vma,
struct file *file, struct address_space *mapping)
{
if (vma->vm_flags & VM_SHARED)
mapping_unmap_writable(mapping);
flush_dcache_mmap_lock(mapping);
vma_interval_tree_remove(vma, &mapping->i_mmap);
flush_dcache_mmap_unlock(mapping);
}
경계 비교의 방향을 source와 맞춥니다
free_pgd_range()는 end - 1 > ceiling - 1이면 end를 한 PMD 단위 줄입니다. 즉 end 쪽이 허용 ceiling을 넘을 때 제한하는 검사입니다. 반대로 ceiling이 end를 넘어서 문제가 생긴다고 읽으면 조건의 방향이 뒤집힙니다. 주소 공간 top을 0으로 나타내는 sentinel 때문에 일반 정수의 end > ceiling로 단순화할 수도 없습니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/memory.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* demand-loading started 01.12.91 - seems it is high on the list of
* things wanted, and it should be easy to implement. - Linus
*/
/*
* Ok, demand-loading was easy, shared pages a little bit tricker. Shared
* pages started 02.12.91, seems to work. - Linus.
*
* Tested sharing by executing about 30 /bin/sh: under the old kernel it
* would have taken more than the 6M I have free, but it worked well as
* far as I could see.
*
* Also corrected some "invalidate()"s - I wasn't doing enough of them.
*/
/*
* Real VM (paging to/from disk) started 18.12.91. Much more work and
* thought has to go into this. Oh, well..
* 19.12.91 - works, somewhat. Sometimes I get faults, don't know why.
* Found it. Everything seems to work now.
* 20.12.91 - Ok, making the swap-device changeable like the root.
*/
/*
* 05.04.94 - Multi-page memory management added for v1.1.
* Idea by Alex Bligh (alex@cconcepts.co.uk)
*
* 16.07.99 - Support of BIGMEM added by Gerhard Wichert, Siemens AG
* (Gerhard.Wichert@pdb.siemens.de)
*
* Aug/Sep 2004 Changed to four level page tables (Andi Kleen)
*/
/* Upstream Linux v6.0: mm/memory.c:343-403
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
void free_pgd_range(struct mmu_gather *tlb,
unsigned long addr, unsigned long end,
unsigned long floor, unsigned long ceiling)
{
pgd_t *pgd;
unsigned long next;
/*
* The next few lines have given us lots of grief...
*
* Why are we testing PMD* at this top level? Because often
* there will be no work to do at all, and we'd prefer not to
* go all the way down to the bottom just to discover that.
*
* Why all these "- 1"s? Because 0 represents both the bottom
* of the address space and the top of it (using -1 for the
* top wouldn't help much: the masks would do the wrong thing).
* The rule is that addr 0 and floor 0 refer to the bottom of
* the address space, but end 0 and ceiling 0 refer to the top
* Comparisons need to use "end - 1" and "ceiling - 1" (though
* that end 0 case should be mythical).
*
* Wherever addr is brought up or ceiling brought down, we must
* be careful to reject "the opposite 0" before it confuses the
* subsequent tests. But what about where end is brought down
* by PMD_SIZE below? no, end can't go down to 0 there.
*
* Whereas we round start (addr) and ceiling down, by different
* masks at different levels, in order to test whether a table
* now has no other vmas using it, so can be freed, we don't
* bother to round floor or end up - the tests don't need that.
*/
addr &= PMD_MASK;
if (addr < floor) {
addr += PMD_SIZE;
if (!addr)
return;
}
if (ceiling) {
ceiling &= PMD_MASK;
if (!ceiling)
return;
}
if (end - 1 > ceiling - 1)
end -= PMD_SIZE;
if (addr > end - 1)
return;
/*
* We add page table cache pages with PAGE_SIZE,
* (see pte_free_tlb()), flush the tlb if we need
*/
tlb_change_page_size(tlb, PAGE_SIZE);
pgd = pgd_offset(tlb->mm, addr);
do {
next = pgd_addr_end(addr, end);
if (pgd_none_or_clear_bad(pgd))
continue;
free_p4d_range(tlb, pgd, addr, next, floor, ceiling);
} while (pgd++, addr = next, addr != end);
}
하위 table 처리 뒤 자신의 parent entry를 clear하고 *_free_tlb()로 넘깁니다. 실제로 할당되지 않은 folded level의 동작은 architecture helper에 달려 있습니다. 아래 P4D·PUD·PMD 함수는 비슷해 보여도 mask, table destructor와 byte accounting 대상이 달라 한 함수로 합쳐 설명하지 않았습니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/memory.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* demand-loading started 01.12.91 - seems it is high on the list of
* things wanted, and it should be easy to implement. - Linus
*/
/*
* Ok, demand-loading was easy, shared pages a little bit tricker. Shared
* pages started 02.12.91, seems to work. - Linus.
*
* Tested sharing by executing about 30 /bin/sh: under the old kernel it
* would have taken more than the 6M I have free, but it worked well as
* far as I could see.
*
* Also corrected some "invalidate()"s - I wasn't doing enough of them.
*/
/*
* Real VM (paging to/from disk) started 18.12.91. Much more work and
* thought has to go into this. Oh, well..
* 19.12.91 - works, somewhat. Sometimes I get faults, don't know why.
* Found it. Everything seems to work now.
* 20.12.91 - Ok, making the swap-device changeable like the root.
*/
/*
* 05.04.94 - Multi-page memory management added for v1.1.
* Idea by Alex Bligh (alex@cconcepts.co.uk)
*
* 16.07.99 - Support of BIGMEM added by Gerhard Wichert, Siemens AG
* (Gerhard.Wichert@pdb.siemens.de)
*
* Aug/Sep 2004 Changed to four level page tables (Andi Kleen)
*/
/* Upstream Linux v6.0: mm/memory.c:307-338
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
static inline void free_p4d_range(struct mmu_gather *tlb, pgd_t *pgd,
unsigned long addr, unsigned long end,
unsigned long floor, unsigned long ceiling)
{
p4d_t *p4d;
unsigned long next;
unsigned long start;
start = addr;
p4d = p4d_offset(pgd, addr);
do {
next = p4d_addr_end(addr, end);
if (p4d_none_or_clear_bad(p4d))
continue;
free_pud_range(tlb, p4d, addr, next, floor, ceiling);
} while (p4d++, addr = next, addr != end);
start &= PGDIR_MASK;
if (start < floor)
return;
if (ceiling) {
ceiling &= PGDIR_MASK;
if (!ceiling)
return;
}
if (end - 1 > ceiling - 1)
return;
p4d = p4d_offset(pgd, start);
pgd_clear(pgd);
p4d_free_tlb(tlb, p4d, start);
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/memory.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* demand-loading started 01.12.91 - seems it is high on the list of
* things wanted, and it should be easy to implement. - Linus
*/
/*
* Ok, demand-loading was easy, shared pages a little bit tricker. Shared
* pages started 02.12.91, seems to work. - Linus.
*
* Tested sharing by executing about 30 /bin/sh: under the old kernel it
* would have taken more than the 6M I have free, but it worked well as
* far as I could see.
*
* Also corrected some "invalidate()"s - I wasn't doing enough of them.
*/
/*
* Real VM (paging to/from disk) started 18.12.91. Much more work and
* thought has to go into this. Oh, well..
* 19.12.91 - works, somewhat. Sometimes I get faults, don't know why.
* Found it. Everything seems to work now.
* 20.12.91 - Ok, making the swap-device changeable like the root.
*/
/*
* 05.04.94 - Multi-page memory management added for v1.1.
* Idea by Alex Bligh (alex@cconcepts.co.uk)
*
* 16.07.99 - Support of BIGMEM added by Gerhard Wichert, Siemens AG
* (Gerhard.Wichert@pdb.siemens.de)
*
* Aug/Sep 2004 Changed to four level page tables (Andi Kleen)
*/
/* Upstream Linux v6.0: mm/memory.c:273-305
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
static inline void free_pud_range(struct mmu_gather *tlb, p4d_t *p4d,
unsigned long addr, unsigned long end,
unsigned long floor, unsigned long ceiling)
{
pud_t *pud;
unsigned long next;
unsigned long start;
start = addr;
pud = pud_offset(p4d, addr);
do {
next = pud_addr_end(addr, end);
if (pud_none_or_clear_bad(pud))
continue;
free_pmd_range(tlb, pud, addr, next, floor, ceiling);
} while (pud++, addr = next, addr != end);
start &= P4D_MASK;
if (start < floor)
return;
if (ceiling) {
ceiling &= P4D_MASK;
if (!ceiling)
return;
}
if (end - 1 > ceiling - 1)
return;
pud = pud_offset(p4d, start);
p4d_clear(p4d);
pud_free_tlb(tlb, pud, start);
mm_dec_nr_puds(tlb->mm);
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/memory.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* demand-loading started 01.12.91 - seems it is high on the list of
* things wanted, and it should be easy to implement. - Linus
*/
/*
* Ok, demand-loading was easy, shared pages a little bit tricker. Shared
* pages started 02.12.91, seems to work. - Linus.
*
* Tested sharing by executing about 30 /bin/sh: under the old kernel it
* would have taken more than the 6M I have free, but it worked well as
* far as I could see.
*
* Also corrected some "invalidate()"s - I wasn't doing enough of them.
*/
/*
* Real VM (paging to/from disk) started 18.12.91. Much more work and
* thought has to go into this. Oh, well..
* 19.12.91 - works, somewhat. Sometimes I get faults, don't know why.
* Found it. Everything seems to work now.
* 20.12.91 - Ok, making the swap-device changeable like the root.
*/
/*
* 05.04.94 - Multi-page memory management added for v1.1.
* Idea by Alex Bligh (alex@cconcepts.co.uk)
*
* 16.07.99 - Support of BIGMEM added by Gerhard Wichert, Siemens AG
* (Gerhard.Wichert@pdb.siemens.de)
*
* Aug/Sep 2004 Changed to four level page tables (Andi Kleen)
*/
/* Upstream Linux v6.0: mm/memory.c:239-271
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
static inline void free_pmd_range(struct mmu_gather *tlb, pud_t *pud,
unsigned long addr, unsigned long end,
unsigned long floor, unsigned long ceiling)
{
pmd_t *pmd;
unsigned long next;
unsigned long start;
start = addr;
pmd = pmd_offset(pud, addr);
do {
next = pmd_addr_end(addr, end);
if (pmd_none_or_clear_bad(pmd))
continue;
free_pte_range(tlb, pmd, addr);
} while (pmd++, addr = next, addr != end);
start &= PUD_MASK;
if (start < floor)
return;
if (ceiling) {
ceiling &= PUD_MASK;
if (!ceiling)
return;
}
if (end - 1 > ceiling - 1)
return;
pmd = pmd_offset(pud, start);
pud_clear(pud);
pmd_free_tlb(tlb, pmd, start);
mm_dec_nr_pmds(tlb->mm);
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/memory.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* demand-loading started 01.12.91 - seems it is high on the list of
* things wanted, and it should be easy to implement. - Linus
*/
/*
* Ok, demand-loading was easy, shared pages a little bit tricker. Shared
* pages started 02.12.91, seems to work. - Linus.
*
* Tested sharing by executing about 30 /bin/sh: under the old kernel it
* would have taken more than the 6M I have free, but it worked well as
* far as I could see.
*
* Also corrected some "invalidate()"s - I wasn't doing enough of them.
*/
/*
* Real VM (paging to/from disk) started 18.12.91. Much more work and
* thought has to go into this. Oh, well..
* 19.12.91 - works, somewhat. Sometimes I get faults, don't know why.
* Found it. Everything seems to work now.
* 20.12.91 - Ok, making the swap-device changeable like the root.
*/
/*
* 05.04.94 - Multi-page memory management added for v1.1.
* Idea by Alex Bligh (alex@cconcepts.co.uk)
*
* 16.07.99 - Support of BIGMEM added by Gerhard Wichert, Siemens AG
* (Gerhard.Wichert@pdb.siemens.de)
*
* Aug/Sep 2004 Changed to four level page tables (Andi Kleen)
*/
/* Upstream Linux v6.0: mm/memory.c:230-237
* Exact source lines; kernel context, not a standalone program or book restoration.
*/
static void free_pte_range(struct mmu_gather *tlb, pmd_t *pmd,
unsigned long addr)
{
pgtable_t token = pmd_pgtable(*pmd);
pmd_clear(pmd);
pte_free_tlb(tlb, token, addr);
mm_dec_nr_ptes(tlb->mm);
}
free_pte_range()의 token은 PTE table의 allocation을 가리킵니다. User data page들을 다시 순회해 put하는 code가 아닙니다. Parent PMD를 clear한 뒤 table lifetime protocol로 넘기고 mm_dec_nr_ptes()로 accounting을 맞춥니다. 실제 physical 재사용까지 안전하려면 hardware walker와 lockless software walker의 조건을 모두 만족해야 합니다.
Source: Linux v6.0 mm/memory.c, mm/mmap.c. 원래 copyright notice와 COPYING, GPL-2.0를 보존했습니다. v6.0을 book 전체의 exact tag로 확정하지 않았고 v6.18은 별도 비교 기준입니다. 이 kernel-context source는 standalone compile·runtime 검증 대상이 아닙니다.
참고 자료
Lorenzo Stoakes, The Linux Memory Manager, Chapter 7 §7.1.5. Linux v6.18 mm/memory.c의 free_pgtables() 계열, table lifetime은 include/asm-generic/tlb.h를 참고하실 수 있습니다.