vfs_caches_init_early()

<kernel v5.0>

VFS 캐시 초기화

vfs_caches_init_early()

fs/dcache.c

void __init vfs_caches_init_early(void)
{
        int i;

        for (i = 0; i < ARRAY_SIZE(in_lookup_hashtable); i++)
                INIT_HLIST_BL_HEAD(&in_lookup_hashtable[i]);

        dcache_init_early();
        inode_init_early();
}

vfs(virtual file system)에서 사용되는 각종 해시 테이블들을 초기화한다.

 

dcache_init_early()

fs/dcache.c

static void __init dcache_init_early(void)
{
        /* If hashes are distributed across NUMA nodes, defer
         * hash allocation until vmalloc space is available.
         */
        if (hashdist)
                return;

        dentry_hashtable =
                alloc_large_system_hash("Dentry cache",
                                        sizeof(struct hlist_bl_head),
                                        dhash_entries,
                                        13,
                                        HASH_EARLY | HASH_ZERO,
                                        &d_hash_shift,
                                        NULL,
                                        0,
                                        0);
        d_hash_shift = 32 - d_hash_shift;
}

Dentry 캐시 해시 리스트를 memblock에 early 할당 받고 초기화한다.

 

inode_init_early()

fs/inode.c

/*
 * Initialize the waitqueues and inode hash table.
 */
void __init inode_init_early(void)
{
        /* If hashes are distributed across NUMA nodes, defer
         * hash allocation until vmalloc space is available.
         */
        if (hashdist)
                return;

        inode_hashtable =
                alloc_large_system_hash("Inode-cache",
                                        sizeof(struct hlist_head),
                                        ihash_entries,
                                        14,
                                        HASH_EARLY | HASH_ZERO,
                                        &i_hash_shift,
                                        &i_hash_mask,
                                        0,
                                        0);
}

Inode 캐시 해시 리스트를 memblock에 early 할당 받고 초기화한다.

 

참고

alloc_large_system_hash()

이 함수를 사용하는 해시명과 사용하는 구조체들은 다음과 같다.

  • “PID”, pid_hash
  • “TCP established”, inet_ehash_bucket
  • “TCP bind”, inet_bind_hashbucket
  • “UDP”, udp_hslot
  • “UDP-Lite”, udp_hslot
  • “futex”, futex_queues
  • “Inode-cache”, hlish_head
  • “Dentry cache” hlist_bl_head
  • “Mount-cache”, hlish_head
  • “Mountpoint-cache”, hlist_head

 

alloc_large_system_hash-1

 

alloc_large_system_hash()

mm/page_alloc.c

/*
 * allocate a large system hash table from bootmem
 * - it is assumed that the hash table must contain an exact power-of-2
 *   quantity of entries
 * - limit is the number of hash buckets, not the total allocation size
 */
void *__init alloc_large_system_hash(const char *tablename,
                                     unsigned long bucketsize,
                                     unsigned long numentries,
                                     int scale,
                                     int flags,
                                     unsigned int *_hash_shift,
                                     unsigned int *_hash_mask,
                                     unsigned long low_limit,
                                     unsigned long high_limit)
{
        unsigned long long max = high_limit;
        unsigned long log2qty, size;
        void *table = NULL;

        /* allow the kernel cmdline to have a say */
        if (!numentries) {
                /* round applicable memory size up to nearest megabyte */
                numentries = nr_kernel_pages;

                /* It isn't necessary when PAGE_SIZE >= 1MB */
                if (PAGE_SHIFT < 20)
                        numentries = round_up(numentries, (1<<20)/PAGE_SIZE);

                /* limit to 1 bucket per 2^scale bytes of low memory */
                if (scale > PAGE_SHIFT)
                        numentries >>= (scale - PAGE_SHIFT);
                else
                        numentries <<= (PAGE_SHIFT - scale);

                /* Make sure we've got at least a 0-order allocation.. */
                if (unlikely(flags & HASH_SMALL)) {
                        /* Makes no sense without HASH_EARLY */
                        WARN_ON(!(flags & HASH_EARLY));
                        if (!(numentries >> *_hash_shift)) {
                                numentries = 1UL << *_hash_shift;
                                BUG_ON(!numentries);
                        }
                } else if (unlikely((numentries * bucketsize) < PAGE_SIZE))
                        numentries = PAGE_SIZE / bucketsize;
        }
        numentries = roundup_pow_of_two(numentries);

인수로 해시 엔트리 수가 0이 입력된 경우 커널 free 페이지 수를 사용하여 최대 수로 해시 엔트리 수를 산출하고 scale 값으로 조정하여 해시 엔트리 수를 결정하되 low ~ high limit 범위로 제한한다.

  •  if (!numentries) {
    • 엔트리 수는 커널의 cmdline에서 커널 파라메터를 사용하여 설정될 수 있다.
      • 예) thash_entries=, uhash_entries=, ihash_entries=, dhash_entries=, mhash_entries=, mphash_entries=
  • numentries = nr_kernel_pages;
    • nr_kernel_pages
      • 커널이 사용할 수 있는 free lowmem page 수
      • setup_arch()->paging_init()->bootmem_init()->zone_sizes_init()->free_area_init_node()->free_area_init_core() 함수에서 설정된다.
  • if (PAGE_SHIFT < 20) numentries = round_up(numentries, (1<<20)/PAGE_SIZE);
    • 페이지 프레임이 1M가 안되는 경우 엔트리 수를 1M/PAGE_SIZE로 round up 한다.
  • if (scale > PAGE_SHIFT) numentries >>= (scale – PAGE_SHIFT);
    • scale이 PAGE_SHIFT보다 큰 경우 엔트리 수를 n(scale – PAGE_SHIFT)으로 나눈다.
      • 예) PID의 경우 scale=18 이므로 페이지 크기와 6 차이가 나므로 산출된 엔트리 수에서 2^6=64로 나눈다.
        • numentries >>= (18 – 12)
  • else numentries <<= (PAGE_SHIFT – scale);
    • 페이지 크기가 scale 크기보다 작은 경우 엔트리 수를 n(PAGE_SHIFT – scalke)으로 곱한다.
  • if (unlikely(flags & HASH_SMALL)) {
    • 작은 확률로 HASH_SMALL 플래그 옵션을 사용한 경우
    • 이 옵션을 사용하는 해시
      • PID 해시
      • futex 해시의 경우 해시 사이즈가 256보다 작은 경우
  • if (!(numentries >> *_hash_shift)) { numentries = 1UL << *_hash_shift; }
    • 엔트리 수가 최소한 _hash_shift 표현 비트보다 크도록 조정한다.
      • PID 해시 예) _hash_shift=4
        • 해시 엔트리 수가 16보다 작은 경우 최소 16으로 조정된다.
  • } else if (unlikely((numentries * bucketsize) < PAGE_SIZE)) numentries = PAGE_SIZE / bucketsize;
    • 작은 확률로 해시 엔트리 수 * 버킷사이즈가 페이지 보다 작은 경우 엔트리 수를 페이지당 버킷사이즈가 들어갈 수 있는 최대 수로 확대 조정한다.
      • 한 페이지도 채우지 못하는 해시 엔트리의 경우 한 페이지를 채우는 수 만큼 확대 조정
  • numentries = roundup_pow_of_two(numentries);
    • 2^n에 가까운 값으로 round up 한다.
      • 예) 4000
        • -> 4096

 

        /* limit allocation size to 1/16 total memory by default */
        if (max == 0) {
                max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
                do_div(max, bucketsize);
        }
        max = min(max, 0x80000000ULL);

        if (numentries < low_limit)
                numentries = low_limit;
        if (numentries > max)
                numentries = max;

        log2qty = ilog2(numentries);

        do {
                size = bucketsize << log2qty;
                if (flags & HASH_EARLY)
                        table = memblock_virt_alloc_nopanic(size, 0);
                else if (hashdist)
                        table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
                else {
                        /*
                         * If bucketsize is not a power-of-two, we may free
                         * some pages at the end of hash table which
                         * alloc_pages_exact() automatically does
                         */
                        if (get_order(size) < MAX_ORDER) {
                                table = alloc_pages_exact(size, GFP_ATOMIC);
                                kmemleak_alloc(table, size, 1, GFP_ATOMIC);
                        }
                }
        } while (!table && size > PAGE_SIZE && --log2qty);

        if (!table)
                panic("Failed to allocate %s hash table\n", tablename);

        printk(KERN_INFO "%s hash table entries: %ld (order: %d, %lu bytes)\n",
               tablename,
               (1UL << log2qty),
               ilog2(size) - PAGE_SHIFT,
               size);

        if (_hash_shift)
                *_hash_shift = log2qty;
        if (_hash_mask)
                *_hash_mask = (1 << log2qty) - 1;

        return table;
}
  • if (max == 0) { max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4; do_div(max, bucketsize); }
    • 인수 high_limit이 지정되지 않은 경우 max(최대 할당 가능 바이트) 값을 산출하여 사용하는데 max를 최대 메모리의 1/16으로 설정 후 다시 max를 bucketsize로 나눈다.
    • do_div(n, base)
      • 64 bit n 값을 32 bit base로 나눈 몫을 n에 저장하고 나머지를 리턴한다.
      • 실제 동작과 달리 코드는 무척 난해하므로 생략한다.
        • 참고: arch/arm/include/asm/div64.h
    • nr_all_pages
      • 전체 메모리 페이지 수가 담긴 전역 변수이다.
      • setup_arch()->paging_init()->bootmem_init()->zone_sizes_init()->free_area_init_node()->free_area_init_core() 함수에서 설정된다.
  • max = min(max, 0x80000000ULL);
    • max 값이 2G를 초과하지 않도록 한다.
  • if (numentries < low_limit) numentries = low_limit;
    • 계산된 해시 엔트리 수가 인수 low_limit 이상이 되게 조정한다.
  • if (numentries > max) numentries = max;
    • 계산된 해시 엔트리 수가 max 이하가 되게 조정한다.
  • log2qty = ilog2(numentries);
    • log2를 계산한다.
    • 예) numentries=120
      • 7

계산된 log2qty bit 수 만큼 메모리 할당을 시도하고 실패하면 반복하여 log2qty bit를 1씩 줄여서 시도한다. 메모리 할당은 다음 3가지 유형을 선택 사용한다.

  • early 요청이 있는 경우 memblock에 할당한다.
  • early 요청이 아니면서 NUMA 및 64비트 시스템인 경우 vmalloc에 할당한다.
  • 그 외의 경우 alloc_pages_exact()를 사용하여 메모리를 할당한다.
    • 내부에서 get_free_pages() 사용

 

  • size = bucketsize << log2qty;
    • 할당할 사이즈는 버킷사이즈를 log2qty 만큼 좌측으로 쉬프트한다.
  • if (flags & HASH_EARLY) table = memblock_virt_alloc_nopanic(size, 0);
    • early 요청이 있는 경우 memblock에 할당한다.
  • else if (hashdist) table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
    • early 요청이 아니면서 NUMA 및 64비트 시스템인 경우 vmalloc에 할당한다.
  • if (get_order(size) < MAX_ORDER) { table = alloc_pages_exact(size, GFP_ATOMIC); kmemleak_alloc(table, size, 1, GFP_ATOMIC); }
    • size 처리 비트가 MAX_ORDER 보다 작은 경우에 한해 size 만큼의 메모리를 alloc_pages_exact()함수를 사용하여 할당한다.
  • } while (!table && size > PAGE_SIZE && –log2qty);
    • 메모리 할당이 실패한 경우 log2qty를 1씩 줄여 할당 공간을 반으로 줄여가며 재 시도한다.
    • size가 PAGE_SIZE 이하가 되면 메모리 할당을 실패한 채로 루프를 빠져나온다.
  • if (!table) panic(“Failed to allocate %s hash table\n”, tablename);
    • 메모리 할당이 실패하면 panic() 코드를 수행한다.
  • 해시 테이블 정보를 출력한다.
    • rpi2 예)
      • PID hash table entries: 4096 (order: 2, 16384 bytes)
      • Dentry cache hash table entries: 131072 (order: 7, 524288 bytes)
      • Inode-cache hash table entries: 65536 (order: 6, 262144 bytes)
      • Mount-cache hash table entries: 2048 (order: 1, 8192 bytes)
      • Mountpoint-cache hash table entries: 2048 (order: 1, 8192 bytes)
      • TCP: Hash tables configured (established 8192 bind 8192)
      • UDP hash table entries: 512 (order: 3, 49152 bytes)
      • UDP-Lite hash table entries: 512 (order: 3, 49152 bytes)
      • futex hash table entries: 1024 (order: 4, 65536 bytes)
  • if (_hash_shift) *_hash_shift = log2qty;
    • _hash_shift가 지정된 경우 _hash_shift값을 업데이트 한다.
  • if (_hash_mask) *_hash_mask = (1 << log2qty) – 1;
    • _hash_mask가 지정된 경우 _hash_mask를 업데이트 한다.

 

참고

 

pidhash_init()

PID 테이블을 해쉬로 구현하여 빠르게 검색하고 처리할 수 있도록 하는데 이 함수를 사용하여 초기화 한다.

pidhash_init-1

pidhash_init()

kernel/pid.c

/*
 * The pid hash table is scaled according to the amount of memory in the
 * machine.  From a minimum of 16 slots up to 4096 slots at one gigabyte or
 * more.
 */
void __init pidhash_init(void)
{
        unsigned int i, pidhash_size;

        pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
                                           HASH_EARLY | HASH_SMALL,
                                           &pidhash_shift, NULL,
                                           0, 4096);
        pidhash_size = 1U << pidhash_shift;

        for (i = 0; i < pidhash_size; i++)
                INIT_HLIST_HEAD(&pid_hash[i]);
}

pid용 해쉬 테이블을 할당하고 초기화한다.

  • pid_hash = alloc_large_system_hash(“PID”, sizeof(*pid_hash), 0, 18, HASH_EARLY | HASH_SMALL, &pidhash_shift, NULL, 0, 4096);
    • 커널 초기화 중이므로 early를 사용하여 memblock에 pid용 해쉬테이블 공간을 할당받는다.
    • low_limit와 high_limit는 0과 4096개로 제한한다.
    • 세 번째 인수로 0이 주어진 경우 커널의 lowmem free 페이지 공간을 확인하여 최대 수의 해시 엔트리 수를 계산해낸다.
    •  HASH_EARLY
      • memblock에 할당 요청
    • HASH_SMALL
      • 최소 엔트리 수인 경우 확대하도록 한다.
      • 해시 엔트리가 최소 2^pidhash_shift 이상 그리고 PAGE_SIZE / pid_hash 사이즈 갯 수 보다 크도록 확대 한다.
    • pid_hash_shift
      • 초기 값은 4
    • rpi2 정보 출력 예)
      • PID hash table entries: 4096 (order: 2, 16384 bytes)
  • pidhash_size = 1U << pidhash_shift;
    • pidhash_size를 2^pidhash_shift로 재조정 한다
    • alloc_large_system_hash()를 수행하면서 결정한 해시 엔트리 수에 따라 전역 pidhash_shift 변수가 재조종된다.
      • rpi2 예)
        • 재조정되어 pidhash_shift=12
  • for (i = 0; i < pidhash_size; i++) INIT_HLIST_HEAD(&pid_hash[i]);
    • pidhash_size 만큼 pid_hash[]를 초기화한다.

 

kernel/pid.c

static struct hlist_head *pid_hash;

 

다음 그림은 pid_hash가 pid 구조체 내부에 있는 upid 구조체들과 연결되는 모습을 보여준다.

pidhash_init-2

 

참고

 

setup_log_buf()

<kernel v5.0>

많은 수의 CPU를 사용하는 SMP 시스템에서 로그 버퍼가 부족해지는 경우가 있어 그러한 시스템에서 더 커진 로그 버퍼를 할당한다.

setup_log_buf-1

 

setup_log_buf()

kernel/printk/printk.c

void __init setup_log_buf(int early)
{
        unsigned long flags;
        char *new_log_buf;
        unsigned int free;

        if (log_buf != __log_buf)
                return;

        if (!early && !new_log_buf_len)
                log_buf_add_cpu();

        if (!new_log_buf_len)
                return;

        if (early) {
                new_log_buf =
                        memblock_alloc(new_log_buf_len, LOG_ALIGN);
        } else {
                new_log_buf = memblock_alloc_nopanic(new_log_buf_len,
                                                          LOG_ALIGN);
        }

        if (unlikely(!new_log_buf)) {
                pr_err("log_buf_len: %lu bytes not available\n",
                        new_log_buf_len);
                return;
        }

        logbuf_lock_irqsave(flags);
        log_buf_len = new_log_buf_len;
        log_buf = new_log_buf;
        new_log_buf_len = 0;
        free = __LOG_BUF_LEN - log_next_idx;
        memcpy(log_buf, __log_buf, __LOG_BUF_LEN);
        logbuf_unlock_irqrestore(flags);

        pr_info("log_buf_len: %u bytes\n", log_buf_len);
        pr_info("early log buf free: %u(%u%%)\n",
                free, (free * 100) / __LOG_BUF_LEN);
}

cpu 수가 적정 수(arm=17개, x86=33)를 초과하는 시스템의 경우 그 cpu 수 만큼 더 커진 새 로그 버퍼를 할당한다.

  • 코드 라인 7~8에서 이미 log_buf가 기본 버퍼를 사용하지 않고 재 설정된 경우 함수를 빠져나간다.
  • 코드 라인 10~11에서 early 호출이 아니면서 new_log_buf_len이 0으로 되어 있는 경우 new_log_buf_len를 재조정한다.
    • 보다 빠르게 로그 버퍼가 필요한 x86시스템에서만 setup_arch() 함수 내부에서 early=1로 하여 호출한다.
    • 정규 호출은 start_kernel()에서 각 아키텍처의 setup_arch() 함수가 완료된 후에 호출한다.
  • 코드 라인 13~14에서 로그 버퍼로 더 추가할 필요가 없는 경우 new_log_buf_len이 여전히 0이며 이 때 함수를 빠져나간다.
  • 코드 라인 16~18에서 early 호출인 경우 new_log_buf를 new_log_buf_len 만큼 할당한다.
    • early 호출 시 memblock 할당이 안되는 경우 panic()이 호출된다.
  • 코드 라인 19~22에서 early 호출이 아닌 경우 new_log_buf를 new_log_buf_len 만큼 할당한다
    • memblock 할당이 안되는 경우에도 panic()이 호출되지 않는다.
  • 코드 라인 34~28에서 적은 확률로 new_log_buf가 설정되지 않으면 에러 메시지를 출력하고 함수를 빠져나간다.
  • 코드 라인 31~33에서 log 버퍼를 새롭게 할당 받은 버퍼로 설정한다.
  • 코드 라인 35에서 원래 로그 버퍼 전체를 새 로그 버퍼로 복사한다.
  • 코드 라인 38~40에서 로그 버퍼 길이 정보를 출력한다.

 

kernel/printk/printk.c

/* record buffer */
#define LOG_ALIGN __alignof__(struct printk_log)
#define __LOG_BUF_LEN (1 << CONFIG_LOG_BUF_SHIFT)
#define LOG_BUF_LEN_MAX (u32)(1 << 31)
static char __log_buf[__LOG_BUF_LEN] __aligned(LOG_ALIGN);
static char *log_buf = __log_buf;
static u32 log_buf_len = __LOG_BUF_LEN;

 

kernel/printk/printk.c

/* requested log_buf_len from kernel cmdline */
static unsigned long __initdata new_log_buf_len;

 

log_buf_add_cpu()

kernel/printk/printk.c

static void __init log_buf_add_cpu(void)
{
        unsigned int cpu_extra;

        /*
         * archs should set up cpu_possible_bits properly with
         * set_cpu_possible() after setup_arch() but just in
         * case lets ensure this is valid.
         */
        if (num_possible_cpus() == 1)
                return;

        cpu_extra = (num_possible_cpus() - 1) * __LOG_CPU_MAX_BUF_LEN;

        /* by default this will only continue through for large > 64 CPUs */
        if (cpu_extra <= __LOG_BUF_LEN / 2)
                return;

        pr_info("log_buf_len individual max cpu contribution: %d bytes\n",
                __LOG_CPU_MAX_BUF_LEN);
        pr_info("log_buf_len total cpu_extra contributions: %d bytes\n",
                cpu_extra);
        pr_info("log_buf_len min size: %d bytes\n", __LOG_BUF_LEN);

        log_buf_len_update(cpu_extra + __LOG_BUF_LEN);
}

default 설정된 로그 버퍼 기준으로 possible cpu 수가 적정 수(arm=17, x86=33)를 초과하는 경우에만 추가 cpu 버퍼를 준비한다.

  • 코드 라인 10~11에서 cpu가 1개일 경우 추가 로그 버퍼를 만들지 않고 함수를 빠져나간다.
  • 코드 라인 13에서 possible cpu-1 만큼의 추가 로그 버퍼를 산출한다.
    • __LOG_CPU_MAX_BUF_LEN
      • default로 4K (2^12)
      • powerpc 아키텍처는 8K(2^13)
  • 코드 라인 16~17에서 추가 로그 버퍼가 기존 로그 버퍼의 절반 보다 작은 경우 추가 버퍼를 만들지 않고 함수를 빠져나간다.
    •  __LOG_BUF_LEN
      • arm 아키텍처는 SoC 마다 8K(2^13) ~ 512K(2^19)를 사용한다.
      • arm64 아키텍처는 128K(2^17)을 사용한다.
      • x86 아키텍처는 256K(2^18)을 사용한다.
  • 코드 라인 19~23에서 추가 버퍼 정보를 출력한다.
  • 코드 라인 25에서  로그 버퍼를 기본 버퍼 + cpu_extra 버퍼 만큼 설정한다.

 

kernel/printk/printk.c

#define __LOG_CPU_MAX_BUF_LEN (1 << CONFIG_LOG_CPU_MAX_BUF_SHIFT)
  • CONFIG_LOG_CPU_MAX_BUF_SHIFT
    • default=12

 

kernel/printk/printk.c

#define __LOG_BUF_LEN (1 << CONFIG_LOG_BUF_SHIFT)
  • CONFIG_LOG_BUF_SHIFT
    • default=17

 

num_possible_cpus()

include/linux/cpumask.h

#define num_possible_cpus()     cpumask_weight(cpu_possible_mask)

possible cpu 수를 알아온다.

 

cpumask_weight()

include/linux/cpumask.h

/**
 * cpumask_weight - Count of bits in *srcp
 * @srcp: the cpumask to count bits (< nr_cpu_ids) in.
 */
static inline unsigned int cpumask_weight(const struct cpumask *srcp)
{
        return bitmap_weight(cpumask_bits(srcp), nr_cpumask_bits);
}

cpu 관련 비트맵 srcp에서 nr_cpumask_bits 만큼의 비트에서 1로 설정된 비트 수를 알아온다.

 

nr_cpumask_bits

include/linux/cpumask.h

#ifdef CONFIG_CPUMASK_OFFSTACK
/* Assuming NR_CPUS is huge, a runtime limit is more efficient.  Also,
 * not all bits may be allocated. */
#define nr_cpumask_bits nr_cpu_ids
#else
#define nr_cpumask_bits NR_CPUS
#endif

 

log_buf_len_update()

kernel/printk/printk.c

/* we practice scaling the ring buffer by powers of 2 */
static void __init log_buf_len_update(unsigned size)
{
        if (size > (u64)LOG_BUF_LEN_MAX) {
                size = (u64)LOG_BUF_LEN_MAX;
                pr_err("log_buf over 2G is not supported.\n");
        }
        if (size)
                size = roundup_pow_of_two(size);
        if (size > log_buf_len)
                new_log_buf_len = size;
}

인수로 지정된 size 값을 가까운 2의 n승에 맞게 round up한 후 new_log_buf_len 보다 큰 경우에만 update 한다. 최대 2G로 제한된다.

  • 예) size=636K
    • 1M

 

/**
 * roundup_pow_of_two - round the given value up to nearest power of two
 * @n - parameter
 *
 * round the given value up to the nearest power of two
 * - the result is undefined when n == 0
 * - this can be used to initialise global variables from constant data
 */
#define roundup_pow_of_two(n)                   \
(                                               \
        __builtin_constant_p(n) ? (             \
                (n == 1) ? 1 :                  \
                (1UL << (ilog2((n) - 1) + 1))   \
                                   ) :          \
        __roundup_pow_of_two(n)                 \
 )

n 값을 가까운 2의 n승에 맞게 round up한 후 리턴한다.

  • 예) 100
    • 128

 

/*
 * round up to nearest power of two
 */
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
        return 1UL << fls_long(n - 1);
}

n 값을 가까운 2의 n승에 맞게 round up한 후 리턴한다.

 

Static Keys -2- (초기화)

<kernel v5.0>

Static Keys -2- (초기화)

커널과 모듈에서 조건문의 branch miss ratio를 낮추어 성능을 향상 시키기 위한 방법으로 static key를 사용한 jump label API를 사용하는데 커널에서 이러한 jump label 코드들을 모두 찾아 초기화한다.

 

static key를 초기화와 관련된 루틴은 다음과 같다.

  • 커널 boot-up – jump_label_init() 함수
  • 모듈 로딩 시 호출될 콜백 함수 등록 – jump_label_init_module()
  • 각 모듈 로딩 시 호출 – jump_label_module_notify()


커널 부트 업 시 Static Key 초기화

 

jump_label_init()

kernel/jump_label.c

void __init jump_label_init(void)
{
        struct jump_entry *iter_start = __start___jump_table;
        struct jump_entry *iter_stop = __stop___jump_table;
        struct static_key *key = NULL;
        struct jump_entry *iter;

        /*
         * Since we are initializing the static_key.enabled field with
         * with the 'raw' int values (to avoid pulling in atomic.h) in
         * jump_label.h, let's make sure that is safe. There are only two
         * cases to check since we initialize to 0 or 1.
         */
        BUILD_BUG_ON((int)ATOMIC_INIT(0) != 0);
        BUILD_BUG_ON((int)ATOMIC_INIT(1) != 1);

        if (static_key_initialized)
                return;

        cpus_read_lock();
        jump_label_lock();
        jump_label_sort_entries(iter_start, iter_stop);

        for (iter = iter_start; iter < iter_stop; iter++) {
                struct static_key *iterk;

                /* rewrite NOPs */
                if (jump_label_type(iter) == JUMP_LABEL_NOP)
                        arch_jump_label_transform_static(iter, JUMP_LABEL_NOP);

                if (init_section_contains((void *)jump_entry_code(iter), 1))
                        jump_entry_set_init(iter);

                iterk = jump_entry_key(iter);
                if (iterk == key)
                        continue;

                key = iterk;
                static_key_set_entries(key, iter);
        }
        static_key_initialized = true;
        jump_label_unlock();
        cpus_read_unlock();
}

jump 라벨의 사용을 위해 초기화를 수행한다. __jump_table에 있는 모든 jump 엔트리를 읽어와서 key로 소팅하고 jump 라벨 타입이 nop인 경우 해당 커널 코드(jump label 코드)의 1 word를 nop으로 rewrite 한다. 그리고 각 static 키들은 각 static 키를 사용하는 첫 jump 엔트리를 가리키게 한다.

  • 코드 라인 17~18에서 static key의 초기화는 한 번만 수행하는 것으로 제한한다.
  • 코드 라인 22에서 __jump_table에 있는 jump 엔트리를 key 주소로 heap sorting을 한다.
  • 코드 라인 24~29에서 __jump_table을 순회하며 jump 라벨 엔트리의 타입이 nop인 경우 static key를 사용한 jump_label API 코드 주소에 nop 명령어를 rewrite 한다.
    • ARM64의 경우는 컴파일 타임에 nop 명령을 사용하여 이미 초기화된 상태라 별도로 nop 코드를 rewrite 할 필요 없다.
  • 코드 라인 31~32에서 jump 엔트리의 코드가 init 섹션안에 위치한 경우라면 key의 bit1을 설정하여 jump 엔트리가 init 섹션안에 위치함을 표시한다. 부트 업이 완료되면 init 섹션안의 코드는 모두 제거된다. 추후 런타임 중에 init 섹션안에 포함된 jump 엔트리들에 대해 업데이트하지 않게 하기 위함이다.
  • 코드 라인 34~36에서 jump 라벨 엔트리들이 key 주소로 sorting 되어 있으므로 동일한 static key를 사용하는 jump 라벨 엔트리인 경우 skip 한다.
  • 코드 라인 38~39에서 새로운 키를 사용하는 jump 엔트리인 경우이다. 이 경우 static 키에 첫 jump 엔트리를 대입한다. 대입할 때 기존 key 타입은 유지한다.
  • 코드 라인 41에서 static key가 모두 초기화 되었음을 알리는 전역 플래그 변수이다.

 

아래 그림은 jump_label_init() 함수를 통해 동작되는 과정을 보여준다.

 

Jump 라벨 엔트리들 소팅

jump_label_sort_entries()

kernel/jump_label.c

static void
jump_label_sort_entries(struct jump_entry *start, struct jump_entry *stop)
{
        unsigned long size;
        void *swapfn = NULL;

        if (IS_ENABLED(CONFIG_HAVE_ARCH_JUMP_LABEL_RELATIVE))
                swapfn = jump_label_swap;

        size = (((unsigned long)stop - (unsigned long)start)
                                        / sizeof(struct jump_entry));
        sort(start, size, sizeof(struct jump_entry), jump_label_cmp, swapfn);
}

__jump_table의 entry를 key 주소로 heap sorting 알고리즘을 수행한다.

 

jump_label_cmp()

kernel/jump_label.c

static int jump_label_cmp(const void *a, const void *b)
{
        const struct jump_entry *jea = a;
        const struct jump_entry *jeb = b;

        if (jump_entry_key(jea) < jump_entry_key(jeb))
                return -1;

        if (jump_entry_key(jea) > jump_entry_key(jeb))
                return 1;

        return 0;
}

두 jump 엔트리의 키를 비교하여 A가 작으면 -1, B가 크면 1, 동일하면 0을 반환한다.

 

jump_label_swap()

kernel/jump_label.c

static void jump_label_swap(void *a, void *b, int size)
{
        long delta = (unsigned long)a - (unsigned long)b;
        struct jump_entry *jea = a;
        struct jump_entry *jeb = b;
        struct jump_entry tmp = *jea;

        jea->code       = jeb->code - delta;
        jea->target     = jeb->target - delta;
        jea->key        = jeb->key - delta;

        jeb->code       = tmp.code + delta;
        jeb->target     = tmp.target + delta;
        jeb->key        = tmp.key + delta;
}

두 jump 엔트리를 swap 한다. ARM64의 경우 CONFIG_HAVE_ARCH_JUMP_LABEL_RELATIVE 커널 옵션을 사용한 상태이므로 두 jump 엔트리 간의 차이 값인 delta가 두 jump 엔트리의 멤버들에 모두 적용된다.

 

jump_label_type()

kernel/jump_label.c

static enum jump_label_type jump_label_type(struct jump_entry *entry)
{
        struct static_key *key = jump_entry_key(entry);
        bool enabled = static_key_enabled(key);
        bool branch = jump_entry_is_branch(entry);

        /* See the comment in linux/jump_label.h */
        return enabled ^ branch;
}

jump 엔트리에서 jump label 타입을 알아온다. 이 타입은 코드에 기록할 타입에 사용한다. (0=JUMP_LABEL_NOP, 1=JUMP_LABEL_JMP)

  • 코드 라인 3에서 jump 엔트리가 가리키는 static 키를 알아온다.
  • 코드 라인 4에서 static 키의 enable 여부를 알아온다.
  • 코드 라인 5에서 jump 엔트리의 nop/branch 여부를 알아온다.
  • 코드 라인 8에서 최종 코드에 적용할 nop/branch 타입을 알아온다.

 

아래 그림은 2가지 상태(초기 설정 상태와 enable 상태)에 따라 nop(JUMP_LABEL_DISABLE)과 branch(JUMP_LABEL_ENABLE) 동작 상태를 기존 API를 사용하여 보여준다.

  • STATIC_KEY_INIT_FALSE 또는 STATIC_KEY_INIT_TRUE로 초기화된 경우는 처음에 항상 nop를 수행하고 static_key_slow_inc() 또는 static_key_slow_dec() 함수에 의해 branch code가 동작하게된다.

jump_label_type-1a

아래 그림은 3가지 상태(초기 설정 상태, enable 상태 및 조건 API)에 따라 nop(JUMP_LABEL_DISABLE)과 branch(JUMP_LABEL_ENABLE) 동작 상태를 신규 API를 사용하여 보여준다.

  • DEFINE_STATIC_KEY_FALSE 또는 DEFINE_STATIC_KEY_TRUE로 초기화된 경우는 static_branch_unlikely() 및 static_branch_likely() 함수와 enable 상태의 조합에 따라 초기 값으로 nop/branch가 결정되고 이후 static_branch_enable() 및 static_branch_disable() API에 의해 조건이 반전된다.

jump_label_type-2a

 

jump_label_init_type()

kernel/jump_label.c

static enum jump_label_type jump_label_init_type(struct jump_entry *entry)
{
        struct static_key *key = jump_entry_key(entry);
        bool type = static_key_type(key);
        bool branch = jump_entry_is_branch(entry);

        /* See the comment in linux/jump_label.h */
        return type ^ branch;
}

jump 엔트리에서 초기 jump label 타입을 알아온다. (0=JUMP_LABEL_NOP, 1=JUMP_LABEL_JMP)

  • 코드 라인 3에서 jump 엔트리가 가리키는 static 키를 알아온다.
  • 코드 라인 4에서 static 키의 타입(true/false)을 알아온다.
  • 코드 라인 5에서 jump 엔트리의 nop/branch 여부를 알아온다.
  • 코드 라인 8에서 초기 코드에 적용된 nop/branch 타입을 산출해 반환한다.

 

static_key_enabled()

include/linux/jump_label.h

#define static_key_enabled(x)                                                   \
({                                                                              \
        if (!__builtin_types_compatible_p(typeof(*x), struct static_key) &&     \
            !__builtin_types_compatible_p(typeof(*x), struct static_key_true) &&\
            !__builtin_types_compatible_p(typeof(*x), struct static_key_false)) \
                ____wrong_branch_error();                                       \
        static_key_count((struct static_key *)x) > 0;                           \
})

static key가 enable 되었는지 여부를 리턴한다.

 

static_key_count()

include/linux/jump_label.h

static inline int static_key_count(struct static_key *key)
{
        return atomic_read(&key->enabled);
}

key->enabled 값을 atomic하게 읽어온다.

 


모듈에서 사용된 static key를 사용한 jump label API

 

다음 그림은 모듈용 jump 라벨 초기화 루틴에서 notifier 블럭을 등록하는 과정을 보여준다.

 

초기화 함수 등록

kernel/jump_label.c

early_initcall(jump_label_init_module);

.initcall 섹션에 jump_label_init_module() 함수를 등록한다.

  • 등록되는 모든 initcall 함수들은 kernel_init 스레드의 do_initcalls() 함수에서 호출된다.

 

early_initcall()

include/linux/init.h

/*      
 * Early initcalls run before initializing SMP.
 *
 * Only for built-in code, not modules.
 */
#define early_initcall(fn)              __define_initcall(fn, early)

 

__define_initcall()

include/linux/init.h

/* initcalls are now grouped by functionality into separate 
 * subsections. Ordering inside the subsections is determined
 * by link order. 
 * For backwards compatibility, initcall() puts the call in 
 * the device init subsection.
 *   
 * The `id' arg to __define_initcall() is needed so that multiple initcalls
 * can point at the same handler without causing duplicate-symbol build errors.
 */  
        
#define __define_initcall(fn, id) \
        static initcall_t __initcall_##fn##id __used \
        __attribute__((__section__(".initcall" #id ".init"))) = fn; \
        LTO_REFERENCE_INITCALL(__initcall_##fn##id)

initcall 함수를 .initcallearly.init 섹션에 등록한다.

  • 예) __initcall_jump_label_init_moduleearly = jump_label_init_module;

 

모듈 로드/언로드

jump_label_init_module()

kernel/jump_label.c

static __init int jump_label_init_module(void)
{
        return register_module_notifier(&jump_label_module_nb);
}

jump_label_module_nb 구조체를 module notifier 블록에 등록한다.

 

jump_label_module_nb 구조체

kernel/jump_label.c

struct notifier_block jump_label_module_nb = {
        .notifier_call = jump_label_module_notify,
        .priority = 1, /* higher than tracepoints */
};
  •  jump_label_module_notify 함수가 등록된다.
  • notifier block이 ascending으로 정렬되어 있고 priority는 1의 값이다.

 


모듈 로딩/언로딩 시 jump 라벨 함수 호출

 

다음 그림은 모듈이 로딩/언로딩될 때마다 등록된 notifier 블럭에 의해 호출되는 jump_label_module_notify() 함수를 보여준다.

 

jump_label_module_notify()

kernel/jump_label.c

static int
jump_label_module_notify(struct notifier_block *self, unsigned long val,
                         void *data)
{
        struct module *mod = data;
        int ret = 0;

        cpus_read_lock();
        jump_label_lock();

        switch (val) {
        case MODULE_STATE_COMING:
                ret = jump_label_add_module(mod);
                if (ret) {
                        WARN(1, "Failed to allocate memory: jump_label may not work properly.\n");
                        jump_label_del_module(mod);
                }
                break;
        case MODULE_STATE_GOING:
                jump_label_del_module(mod);
                break;
        }

        jump_label_unlock();
        cpus_read_unlock();

        return notifier_from_errno(ret);
}

개개 모듈이 로드/언로드/초기화 되었을 때 각각 호출되며 3가지 메시지에 대해 아래의 메시지에 대해 구분하여 처리된다.

  • MODULE_STATE_COMING
    • 모듈이 로드 되었을 때 호출되는 이벤트로 static key에 static_key_module 객체를 할당하여 연결한다.
    • load_module() 함수에서 notifier_call_chain()을 호출한다.
  • MODULE_STATE_GOING
    • 모듈이 언로드 되었을 때 호출되는 이벤트로 static key에 연결된 static_key_module  객체들 중 해당 모듈이 있는 객체를 찾아 삭제한다.
    • delete_module() 함수에서 notifier_call_chain()을 호출한다.

 

모듈 로딩 시 jump 라벨 초기화

jump_label_add_module()

kernel/jump_label.c

static int jump_label_add_module(struct module *mod)
{
        struct jump_entry *iter_start = mod->jump_entries;
        struct jump_entry *iter_stop = iter_start + mod->num_jump_entries;
        struct jump_entry *iter;
        struct static_key *key = NULL;
        struct static_key_mod *jlm, *jlm2;

        /* if the module doesn't have jump label entries, just return */
        if (iter_start == iter_stop)
                return 0;

        jump_label_sort_entries(iter_start, iter_stop);

        for (iter = iter_start; iter < iter_stop; iter++) {
                struct static_key *iterk;

                if (within_module_init(jump_entry_code(iter), mod))
                        jump_entry_set_init(iter);

                iterk = jump_entry_key(iter);
                if (iterk == key)
                        continue;

                key = iterk;
                if (within_module((unsigned long)key, mod)) {
                        static_key_set_entries(key, iter);
                        continue;
                }
                jlm = kzalloc(sizeof(struct static_key_mod), GFP_KERNEL);
                if (!jlm)
                        return -ENOMEM;
                if (!static_key_linked(key)) {
                        jlm2 = kzalloc(sizeof(struct static_key_mod),
                                       GFP_KERNEL);
                        if (!jlm2) {
                                kfree(jlm);
                                return -ENOMEM;
                        }
                        preempt_disable();
                        jlm2->mod = __module_address((unsigned long)key);
                        preempt_enable();
                        jlm2->entries = static_key_entries(key);
                        jlm2->next = NULL;
                        static_key_set_mod(key, jlm2);
                        static_key_set_linked(key);
                }
                jlm->mod = mod;
                jlm->entries = iter;
                jlm->next = static_key_mod(key);
                static_key_set_mod(key, jlm);
                static_key_set_linked(key);

                /* Only update if we've changed from our initial state */
                if (jump_label_type(iter) != jump_label_init_type(iter))
                        __jump_label_update(key, iter, iter_stop, true);
        }

        return 0;
}

모듈에서 사용하는 jump label 엔트리를 정렬(heap sort) 한다. 그리고 static 키가 해당 모듈에 이미 포함되어 있는 경우 key->entries가 해당 엔트리를 가리키게 하고, 그렇지 않은 경우 글로벌 static 키가 커널에 존재하므로 static_key_mod  객체를 할당하고 이를 key에 연결한다. 그런 후 타입이 enable인 경우 동일한 키를 사용하는 모든 엔트리가 가리키는 code  주소의 명령을 update 한다.

  • 코드 라인 10~11에서 jump 라벨을 사용하지 않은 모듈인 경우 그냥 함수를 빠져나간다.
  • 코드 라인 13에서 모듈에 존재하는 jump label 엔트리를 정렬(heap sort)한다.
  • 코드 라인 15~19에서 모듈에 있는 jump label 엔트리를 순회하며 jump 라벨이 모듈의 init 섹션에서 사용된 경우 이를 식별하기 위해 key의 bit1을 설정한다.
  • 코드 라인 21~23에서 이미 처리한 static 키와 연결된 jump 라벨 엔트리는 skip 한다.
  • 코드 라인 25~29에서 소팅된 jump 라벨 엔트리들 중 static 키와 연결된 첫 jump 라벨 엔트리이다. 여기서 static 키가 모듈에서 정의된 경우 해당 static 키를 첫 jump 라벨 엔트리에 연결한다.
  • 코드 라인 30~32에서 jump 라벨이 모듈 외부의 커널에서 정의된 static를 사용하는 경우이다. 이 모듈을 커널의 static 키에 연결하기 위해 static_key_mod 구조체를 할당받는다.
  • 코드 라인 33~47에서 커널의 static 키가 한 번도 모듈과 링크를 한 적이 없으면 static_key_mod 구조체를 추가로 하나 더 만들고 이를 먼저 연결한다.
  • 코드 라인 48~52에서 static_key_mod 구조체의 내용을 채운 후 커널의 글로벌 static 키가 사용하는 static_key_mod에 연결한다.
  • 코드 라인 55~56에서 jump 라벨의 초기값과 jump 라벨 타입이 다른 경우에 한해 이에 해당하는 jump 라벨들이 가리키는 코드들을 모두 update 한다.

 

다음 그림은 module-B가 로드되어 static key를 사용한 jump 라벨들이 초기화되는 과정을 보여준다.

  • static_key_mod 객체가 추가되고 추가된 모듈은 module을 가리키고 entries 멤버는 해당 모듈의 해당 static 키를 사용한 첫 jump 라벨 엔트리를 가리킨다.
  • 모듈 내부의 각 static key는 해당 static 키를 사용하는 첫 jump 라벨 엔트리를 가리킨다.

 

모듈 언로딩 시 jump 라벨 정리

jump_label_del_module()

kernel/jump_label.c

static void jump_label_del_module(struct module *mod)
{
        struct jump_entry *iter_start = mod->jump_entries;
        struct jump_entry *iter_stop = iter_start + mod->num_jump_entries;
        struct jump_entry *iter;
        struct static_key *key = NULL;
        struct static_key_mod *jlm, **prev;

        for (iter = iter_start; iter < iter_stop; iter++) {
                if (jump_entry_key(iter) == key)
                        continue;

                key = jump_entry_key(iter);

                if (within_module((unsigned long)key, mod))
                        continue;

                /* No memory during module load */
                if (WARN_ON(!static_key_linked(key)))
                        continue;

                prev = &key->next;
                jlm = static_key_mod(key);

                while (jlm && jlm->mod != mod) {
                        prev = &jlm->next;
                        jlm = jlm->next;
                }

                /* No memory during module load */
                if (WARN_ON(!jlm))
                        continue;

                if (prev == &key->next)
                        static_key_set_mod(key, jlm->next);
                else
                        *prev = jlm->next;

                kfree(jlm);

                jlm = static_key_mod(key);
                /* if only one etry is left, fold it back into the static_key */
                if (jlm->next == NULL) {
                        static_key_set_entries(key, jlm->entries);
                        static_key_clear_linked(key);
                        kfree(jlm);
                }
        }
}

모듈에서 사용한 외부 글로벌 static key를 찾고 여기에 연결된 static_key_mod 객체를 찾아 연결을 끊고 메모리를 해지한다.

  • 코드 라인 9~11에서 모듈에 있는 key 값으로 소팅된 jump label 엔트리 수 만큼 순회하며 동일한 static 키를 사용하는 jump 라벨 엔트리는 처리하지 않기 위해 skip 한다.
  • 코드 라인 13~16에서 jump 라벨 엔트리가 모듈내에 정의된 static 키를 사용하는 경우 skip 한다.
  • 코드 라인 19~20에서 글로벌 static 키가 링크된 적이 없으면 경고 메시지를 출력하고 skip 한다.
  • 코드 라인 22~32에서 언로드될 모듈에 연결될 static_key_mod 구조체를 순차 검색한다.
  • 코드 라인 34~39에서 해당 static_key_mod 구조체의 연결을 끊고 메모리를 해제한다.
  • 코드 라인 41~47에서 만일 static 키에 연결된 static_key_mod 객체가 하나만 남은 경우 마저 제거하고 할당 해제한다. 이 때 마지막 객체에 연결된 글로벌 jump 라벨 엔트리는 static 키에 다시 연결한다. 연결 시 link 플래그는 제거한다.

 

다음 그림은 module-B가 언로드될 때 static 키 모듈 연결 정보인 static_key_mod 객체를 소멸시키는 과정을 보여준다.

 

참고