Slub Memory Allocator -7- (Drain/Flush 캐시)

 

Drain 캐시

deactivate_slab()

mm/slub.c

/*
 * Remove the cpu slab
 */
static void deactivate_slab(struct kmem_cache *s, struct page *page,
                                void *freelist)
{
        enum slab_modes { M_NONE, M_PARTIAL, M_FULL, M_FREE };
        struct kmem_cache_node *n = get_node(s, page_to_nid(page));
        int lock = 0;
        enum slab_modes l = M_NONE, m = M_NONE;
        void *nextfree;
        int tail = DEACTIVATE_TO_HEAD;
        struct page new;
        struct page old;

        if (page->freelist) {
                stat(s, DEACTIVATE_REMOTE_FREES);
                tail = DEACTIVATE_TO_TAIL;
        }

        /*
         * Stage one: Free all available per cpu objects back
         * to the page freelist while it is still frozen. Leave the
         * last one.
         *
         * There is no need to take the list->lock because the page
         * is still frozen.
         */
        while (freelist && (nextfree = get_freepointer(s, freelist))) {
                void *prior;
                unsigned long counters;

                do {
                        prior = page->freelist;
                        counters = page->counters;
                        set_freepointer(s, freelist, prior);
                        new.counters = counters;
                        new.inuse--;
                        VM_BUG_ON(!new.frozen);

                } while (!__cmpxchg_double_slab(s, page,
                        prior, counters,
                        freelist, new.counters,
                        "drain percpu freelist"));

                freelist = nextfree;
        }

 

리모트 cpu에서 free object를 한 흔적이 남아 있는 경우 slub page를 per 노드의 partial 리스트의 후미에 들어갈 수 있도록 설정한다.

  •  struct kmem_cache_node *n = get_node(s, page_to_nid(page));
    • per 노드를 알아온다.
  • if (page->freelist) { stat(s, DEACTIVATE_REMOTE_FREES); tail = DEACTIVATE_TO_TAIL; }
    • page에 free objects들이 있는 경우 DEACTIVASTE_REMOTE_FREES stat을 증가시킨다.
      • remote cpu에서 object를 free한 경우 page->freelist에 free object가 존재할 수 있다. 결국 remote cpu가 처리한 페이지 이므로 가능하면 현재 cpu가 접근하게 되는 확률을 늦추게 하기 위해 per 노드의 partial 리스트의 마지막에 추가(cold 처리)한다.

 

Stage 1: per cpu 캐시의 freelist에 있는 전체 object들 중 마지막 object를 제외하고 page->freelist로 모두 옮긴다.

  •  while (freelist && (nextfree = get_freepointer(s, freelist))) {
    • 현재 free object와 다음 free object가 존재하는 동안
      • 마지막 object 하나만 제외하고 루프를 돈다.
  • do { prior = page->freelist; counters = page->counters; set_freepointer(s, freelist, prior); new.counters = counters; new.inuse–;
    • per cpu 캐시의 freelist의 첫 object에 대해 per cpu 캐시의 page->freelist로 옮길 준비를 한다.
  • } while (!__cmpxchg_double_slab(s, page, prior, counters, freelist, new.counters, “drain percpu freelist”));
    • object를 per cpu 캐시의 page->freelist로 옮긴다.
  • freelist = nextfree; }
    • 다음 freeobject를 처리하기 위해 준비하고 루프로 되돌아간다.

 

        /*
         * Stage two: Ensure that the page is unfrozen while the
         * list presence reflects the actual number of objects
         * during unfreeze.
         *
         * We setup the list membership and then perform a cmpxchg
         * with the count. If there is a mismatch then the page
         * is not unfrozen but the page is on the wrong list.
         *
         * Then we restart the process which may have to remove
         * the page from the list that we just put it on again
         * because the number of objects in the slab may have
         * changed.
         */
redo:

        old.freelist = page->freelist;
        old.counters = page->counters;
        VM_BUG_ON(!old.frozen);

        /* Determine target state of the slab */
        new.counters = old.counters;
        if (freelist) {
                new.inuse--;
                set_freepointer(s, freelist, old.freelist);
                new.freelist = freelist;
        } else
                new.freelist = old.freelist;

        new.frozen = 0;

        if (!new.inuse && n->nr_partial >= s->min_partial)
                m = M_FREE;
        else if (new.freelist) {
                m = M_PARTIAL;
                if (!lock) {
                        lock = 1;
                        /*
                         * Taking the spinlock removes the possiblity
                         * that acquire_slab() will see a slab page that
                         * is frozen
                         */
                        spin_lock(&n->list_lock);
                }
        } else {
                m = M_FULL;
                if (kmem_cache_debug(s) && !lock) {
                        lock = 1;
                        /*
                         * This also ensures that the scanning of full
                         * slabs from diagnostic functions will not see
                         * any frozen slabs.
                         */
                        spin_lock(&n->list_lock);
                }
        }

Stage 2: 최초 이 루틴에 진입하는 경우 frozen 상태에서 아직 하나의 object 처리가 남아 있는 상태이다. 이 상태에서 상황에 따라서 slub page를 해지하여 버디시스템으로 돌려줄 수도 있고 per 노드의 partial 리스트나 slub 디버깅에서 사용하는 full 리스트로 옮길 수도 있으므로 준비한다.

  • redo:
    • slub page의 freelist 및 unfrozen에 대한 atomic operation이 실패하면 다시 돌아오게되는 레이블
  • old.freelist = page->freelist; old.counters = page->counters;
    • old 변수에 현재 slub page의 freelist와 카운터(inuse, objects, frozen bit)를 백업해둔다.
  • new.counters = old.counters;
    • 바뀔 카운터를 준비한다.
  • if (freelist) { new.inuse–; set_freepointer(s, freelist, old.freelist); new.freelist = freelist;
    • 인수 freelist에 값이 있는 경우(처리할 잔존 object가 존재하는 경우) 사용 object 수를 감소시키고 slub page의 선두에 insert할 준비를 한다.
  • } else new.freelist = old.freelist;
    • 처리할 잔존 object가 없는 경우는 slub page의 freelist 값은 기존 값 그대로 바꿀 계획이다.
      • 이 값이 나중에 비교해서 다른 경우 atomic operation이 실패하게 된다.
  • new.frozen = 0; if (!new.inuse && n->nr_partial >= s->min_partial) m = M_FREE;
    • unfrozen 상태로 바꿀 준비를 하고 사용중인 object가 없으면서 per 노드의 partial 리스트의 slub page 최소 한계(s->min_partial)를 초과한 경우 slub page를 해제하여 버디 시스템으로 돌리게 하기 위해 현재 slub 모드 상태 m을 M_FREE로 한다.
  • else if (new.freelist) { m = M_PARTIAL;
    • slub page에 free object가 있는 경우 per 노드의 partial 리스트에 추가될 계획으로 현재 slub 모드 상태 m을 M_PARTIAL로 한다.
  • } else { m = M_FULL;
    • slub page에 free object가 하나도 없는 경우 per 노드의 full 리스트에 추가될 계획으로 현재 slub 모드 상태 m을 M_FULL로 한다.

 

        if (l != m) {

                if (l == M_PARTIAL)

                        remove_partial(n, page);

                else if (l == M_FULL)

                        remove_full(s, n, page);

                if (m == M_PARTIAL) {

                        add_partial(n, page, tail);
                        stat(s, tail);

                } else if (m == M_FULL) {

                        stat(s, DEACTIVATE_FULL);
                        add_full(s, n, page);

                }
        }

        l = m;
        if (!__cmpxchg_double_slab(s, page,
                                old.freelist, old.counters,
                                new.freelist, new.counters,
                                "unfreezing slab"))
                goto redo;

        if (lock)
                spin_unlock(&n->list_lock);

        if (m == M_FREE) {
                stat(s, DEACTIVATE_EMPTY);
                discard_slab(s, page);
                stat(s, FREE_SLAB);
        }
}

slub page를 unfrozen 시키면서 기존 slub 모드 상태 l과 현재 slub 모드 상태 m에 따라 다음과 같이 slub page에 따른 처리를 하되 실패하는 경우 다시 Stage 2 과정부터 돌아가서 처리한다.

  • per 노드의 partial 리스트에 추가 또는 삭제
  • per 노드의 full 리스트에 추가  또는 식제
  • slub page를 해제하여 버디 시스템으로 돌려주기

 

  • if (l == M_PARTIAL) remove_partial(n, page);
    • slub page를 per 노드의 partial 리스트에 추가하였던 것을 상태가 바뀌어 다시 제거한다.
      • page가 frozen 상태에 있는 경우 free object들의 할당과 해제가 경쟁상태에서 계속되고 있다.
    • else if (l == M_FULL) remove_full(s, n, page);
      • slub page를 per 노드의 full 리스트에 추가하였던 것을 상태가 바뀌어 다시 제거한다.
    • if (m == M_PARTIAL) { add_partial(n, page, tail); stat(s, tail);
      • slub page에 freelist가 생긴 경우 per 노드의 partial 리스트에 추가한다.
    • } else if (m == M_FULL) { stat(s, DEACTIVATE_FULL); add_full(s, n, page); }
      • slub page에 freelist가 없는 경우 DEACTIVATE_FULL stat을 증가시킨다. add_full(0 함수는 slub 디버그 상태에서 사용된다.
    • l = m; if (!__cmpxchg_double_slab(s, page, old.freelist, old.counters, new.freelist, new.counters, “unfreezing slab”))
      • slab 모드를 동일하게 하고, slub page의 freelist를 준비한 상태와 다름이 없게 frozen 시키면서 갱신하고, 만일 갱신이 실패한 경우 redo 레이블부터 다시 시도하다.
        • slub object들의 경쟁이 가능한 frozen 상태라서 slub page의 freelist에 있는 object가 다시 할당 받아 없어졌거나, 리모트 cpu로부터 할당 해지되어 이 slub page에 추가되는 등의 변동이 가능하다.
    • if (lock) spin_unlock(&n->list_lock);
      • 그 동안 lock이 걸린 경우 해제한다.
    • if (m == M_FREE) { stat(s, DEACTIVATE_EMPTY); discard_slab(s, page); stat(s, FREE_SLAB); }
      • 최종 바뀐 slub 모드가 모든 object가 free된 상태이면 slub page를 버디 시스템에 다시 되돌려 준다.

 

아래 그림은 per cpu 캐시에 있는 frozen된 slub page를 노드로 옮기는 과정을 보여준다. (한 번에 성공을 한 case)

deactivate_slab-1

 

Flush 캐시

flush_all()

mm/slub.c

static void flush_all(struct kmem_cache *s)
{
        on_each_cpu_cond(has_cpu_slab, flush_cpu_slab, s, 1, GFP_ATOMIC);
}

online된 cpu들에서 cpu_slab이 존재하는 경우 cpu_slab을 flush 하도록 각 cpu에 요청하고 완료될 때 까지 기다린다.

 

아래 그림은 online된 cpu 4개에 대해 cpu_slab이 존재하는 경우 flush 시키는 것을 보여준다.

flush_all-1

 

on_each_cpu_cond()

kernel/smp.c

/*
 * on_each_cpu_cond(): Call a function on each processor for which
 * the supplied function cond_func returns true, optionally waiting
 * for all the required CPUs to finish. This may include the local
 * processor.
 * @cond_func:  A callback function that is passed a cpu id and
 *              the the info parameter. The function is called
 *              with preemption disabled. The function should
 *              return a blooean value indicating whether to IPI
 *              the specified CPU.
 * @func:       The function to run on all applicable CPUs.
 *              This must be fast and non-blocking.
 * @info:       An arbitrary pointer to pass to both functions.
 * @wait:       If true, wait (atomically) until function has
 *              completed on other CPUs.
 * @gfp_flags:  GFP flags to use when allocating the cpumask
 *              used internally by the function.
 *
 * The function might sleep if the GFP flags indicates a non
 * atomic allocation is allowed. 
 *
 * Preemption is disabled to protect against CPUs going offline but not online.
 * CPUs going online during the call will not be seen or sent an IPI.
 *
 * You must not call this function with disabled interrupts or
 * from a hardware interrupt handler or from a bottom half handler.
 */
void on_each_cpu_cond(bool (*cond_func)(int cpu, void *info),
                        smp_call_func_t func, void *info, bool wait,
                        gfp_t gfp_flags)
{
        cpumask_var_t cpus; 
        int cpu, ret;

        might_sleep_if(gfp_flags & __GFP_WAIT);

        if (likely(zalloc_cpumask_var(&cpus, (gfp_flags|__GFP_NOWARN)))) {
                preempt_disable();
                for_each_online_cpu(cpu)
                        if (cond_func(cpu, info))
                                cpumask_set_cpu(cpu, cpus);
                on_each_cpu_mask(cpus, func, info, wait);
                preempt_enable();
                free_cpumask_var(cpus);
        } else {
                /*
                 * No free cpumask, bother. No matter, we'll
                 * just have to IPI them one by one.
                 */
                preempt_disable();
                for_each_online_cpu(cpu)
                        if (cond_func(cpu, info)) {
                                ret = smp_call_function_single(cpu, func,
                                                                info, wait);
                                WARN_ON_ONCE(ret);
                        }
                preempt_enable();
        }
}
EXPORT_SYMBOL(on_each_cpu_cond);

online된 cpu들에서 인수로 받은 cond_func() 함수 결과가 true인 경우 인수로 받은 func() 함수를 수행하게 한다. 그리고 wait이 true인 경우 현재 cpu에서 각 cpu로 보낸 함수의 실행 요청에 대한 완료를 기다린다.

  •  might_sleep_if(gfp_flags & __GFP_WAIT);
    • __GFP_WAIT 플래그 옵션이 요청된 경우 높은 우선 순위의 task로부터 preemption 요청이 있는 경우 리스케쥴링을 허용하고 현재 task는 slepp한다.
  • if (likely(zalloc_cpumask_var(&cpus, (gfp_flags|__GFP_NOWARN)))) {
    • cpu 비트맵을 클리어한다. CONFIG_CPUMASK_OFFSTACK 옵션이 사용된 경우 cpu 비트맵을 할당받는다.
    • CONFIG_CPUMASK_OFFSTACK 커널 옵션
      • CPU 디버깅을 위해 DEBUG_PER_CPU_MAPS 커널 옵션을 사용하는 경우에 사용할 수 있는 커널 옵션이다.
      • 이 옵션은 CPU 마스크를 stack을 이용하지 않고 dynamic하게 별도의 메모리 할당을 받아 사용하므로 zalloc_cpumask_var() 함수로 인해서 stack overflow가 발생하지 않는 장점이 있으나 단점으로는 속도가 저하된다.
  • for_each_online_cpu(cpu) if (cond_func(cpu, info)) cpumask_set_cpu(cpu, cpus);
    • online cpu 수 만큼 루프를 돌며 인수로 전달받은 비교함수가 true인 경우 cpus 비트맵의 현재 cpu 비트를 설정한다.
  • on_each_cpu_mask(cpus, func, info, wait);
    • cpus 비트맵에 설정된 모든 cpu에서 func 함수를 수행한다. wait이 true인 경우 각 함수의 실행 완료를 기다린다.
  • if (cond_func(cpu, info)) { ret = smp_call_function_single(cpu, func, info, wait); }
    • zalloc_cpumask_var()를 통해 메모리 할당이 안된 경우 online된 cpu에 대해 루프를 돌며 인수로 전달받은 비교함수 cond_func()가 true인 경우 해당 cpu에서 func 함수를 동작시키게 요청한다.

 

has_cpu_slab()

mm/slub.c

static bool has_cpu_slab(int cpu, void *info)
{
        struct kmem_cache *s = info;
        struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);

        return c->page || c->partial;
}

cpu_slab의 유무를 반환한다.

 

on_each_cpu_mask()

kernel/smp.c

void on_each_cpu_mask(const struct cpumask *mask, smp_call_func_t func,
                        void *info, bool wait)
{
        int cpu = get_cpu();

        smp_call_function_many(mask, func, info, wait);
        if (cpumask_test_cpu(cpu, mask)) {
                unsigned long flags;
                local_irq_save(flags);
                func(info);
                local_irq_restore(flags);
        }
        put_cpu();
}
EXPORT_SYMBOL(on_each_cpu_mask);

cpu 비트맵에 설정된 모든 cpu에서 func 함수를 수행한다. wait이 true인 경우 각 함수의 실행 완료를 기다린다.

  • smp_call_function_many(mask, func, info, wait);
    • 현재 cpu를 제외한 다른 cpu 모두에서 func 함수가 실행되게 한다. wait 인수를 true로 지정하는 경우 현재 cpus는 각 cpu의 함수 실행이 완료될 때 까지 기다린다.
    • 참고: IPI cross call – 소프트 인터럽트 | 문c
  • if (cpumask_test_cpu(cpu, mask)) { func(info); }
    • 현재 cpu도 마스크 되어 있는 경우 func 함수를 실행한다.

 

flush_cpu_slab()

mm/slub.c

static void flush_cpu_slab(void *d)
{
        struct kmem_cache *s = d;

        __flush_cpu_slab(s, smp_processor_id());
}

 

__flush_cpu_slab()

mm/slub.c

/*
 * Flush cpu slab.
 *
 * Called from IPI handler with interrupts disabled.
 */
static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu)
{
        struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);

        if (likely(c)) {
                if (c->page)
                        flush_slab(s, c);

                unfreeze_partials(s, c);
        }
}

이 함수는 각 CPU의 IPI 핸들러가 호출되고 수행되어지는 함수이며 반드시 인터럽트는 disable된 채로 호출되야 한다.  cpu_slab 페이지가 존재하는 경우 slab(slub)을 flush하고 모든 partial된 slab(slub)을 unfreeze 한다.

 

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.