Slub Memory Allocator -6- (Object 해제)

지정한 kmem_cache의 slub page에서 slab(slub) object를 해제한다.


다음 그림은 slub object를 해제할 때 호출되는 함수들의 흐름을 보여준다.





void kmem_cache_free(struct kmem_cache *s, void *x)
        s = cache_from_obj(s, x);
        if (!s)
        slab_free(s, virt_to_head_page(x), x, _RET_IP_);
        trace_kmem_cache_free(_RET_IP_, x);

slub object를 free한다.

  • s = cache_from_obj(s, x); if (!s) return;
    • slub object로 캐시를 알아오는데 null인 경우 처리하지 않고 빠져나간다.
  • slab_free(s, virt_to_head_page(x), x, _RET_IP_);
    • slub object를 free한다.




static inline struct kmem_cache *cache_from_obj(struct kmem_cache *s, void *x)
        struct kmem_cache *cachep;
        struct page *page;

         * When kmemcg is not being used, both assignments should return the
         * same value. but we don't want to pay the assignment price in that
         * case. If it is not compiled in, the compiler should be smart enough
         * to not do even the assignment. In that case, slab_equal_or_root
         * will also be a constant.
        if (!memcg_kmem_enabled() && !unlikely(s->flags & SLAB_DEBUG_FREE))
                return s;
        page = virt_to_head_page(x);
        cachep = page->slab_cache;
        if (slab_equal_or_root(cachep, s))
                return cachep;
        pr_err("%s: Wrong slab cache. %s but object is from %s\n",
               __func__, cachep->name, s->name);
        return s;

slub object로 캐시를 알아온다. 만일 인수로 지정된 캐시가 알아온 캐시와 다르거나 루트 캐시가 아닌 경우 에러 메시지를 출력하고 인수로 지정된 캐시를 반환한다.

  • 인수로 지정된 캐시가 반환되지 않는 경우는 인수로 지정한 캐시가 루트 캐시인 경우이다.
  • if (!memcg_kmem_enabled() && !unlikely(s->flags & SLAB_DEBUG_FREE)) return s;
    • memcg를 활성화시키지 않았으면서 작은 확률로 SLAB_DEBUG_FREE 플래그를 사용하지 않은 경우 주어진 캐시를 그냥 반환한다.
  • page = virt_to_head_page(x);
    • head 페이지를 알아온다.
  •  cachep = page->slab_cache;
    • 캐시 주소를 알아온다.
  • if (slab_equal_or_root(cachep, s)) return cachep;
    • 알아온 캐시 주소가 인수로 주어진 캐시와 똑같거나 루트 캐시인 경우 반환한다.
  • pr_err(“%s: Wrong slab cache. %s but object is from %s\n”, __func__, cachep->name, s->name);
    • 지정된 캐시가 잘못된 경우 에러 메시지를 출력하고 알아온 캐시를 반환한다.




 * Fastpath with forced inlining to produce a kfree and kmem_cache_free that
 * can perform fastpath freeing without additional function calls.
 * The fastpath is only possible if we are freeing to the current cpu slab
 * of this processor. This typically the case if we have just allocated
 * the item before.
 * If fastpath is not possible then fall back to __slab_free where we deal
 * with all sorts of special processing.
static __always_inline void slab_free(struct kmem_cache *s,
                        struct page *page, void *x, unsigned long addr)
        void **object = (void *)x;
        struct kmem_cache_cpu *c;
        unsigned long tid;

        slab_free_hook(s, x);

         * Determine the currently cpus per cpu slab.
         * The cpu may change afterward. However that does not matter since
         * data is retrieved via this pointer. If we are on the same cpu
         * during the cmpxchg then the free will succedd.
        do {
                tid = this_cpu_read(s->cpu_slab->tid);
                c = raw_cpu_ptr(s->cpu_slab);
        } while (IS_ENABLED(CONFIG_PREEMPT) &&
                 unlikely(tid != READ_ONCE(c->tid)));

        /* Same with comment on barrier() in slab_alloc_node() */

        if (likely(page == c->page)) {
                set_freepointer(s, object, c->freelist);

                if (unlikely(!this_cpu_cmpxchg_double(
                                s->cpu_slab->freelist, s->cpu_slab->tid,
                                c->freelist, tid,
                                object, next_tid(tid)))) {

                        note_cmpxchg_failure("slab_free", s, tid);
                        goto redo;
                stat(s, FREE_FASTPATH);
        } else
                __slab_free(s, page, x, addr);

  • redo:
    • atomic operation이 실패하는 경우 다시 시도하기 위해 이동해 올 레이블
  • do { tid = this_cpu_read(s->cpu_slab->tid); c = raw_cpu_ptr(s->cpu_slab); } while (IS_ENABLED(CONFIG_PREEMPT) && unlikely(tid != READ_ONCE(c->tid)));
    • per cpu 캐시의 tid 값과 per cpu 캐시를 알아온다.
      • CONFIG_PREEMPT 커널 옵션을 사용하는 커널은 현재 이 시점에서 preemption이 언제라도 가능하기 때문에 수행 중 태스크 전환되었다 다시 돌아왔을 수 있고, 다른 cpu에서 동시에 같은 캐시에 object를 할당 또는 해제하려 할 수 있다. 따라서 이 루틴에서는 tid를 살펴서 변화가 없음을 확인하여 같은 cpu에서 동작하는 것을 보장하고 또한 같은 캐시에서 다른 cpu와 경쟁 상태가 아님을 보장하게 확인하는 과정이다.
  • if (likely(page == c->page)) {
    • 높은 확률로 slub page가 per cpu 캐시 page와 같은 경우
      • preemption되지 않은 경우(preemption 되었다가 다시 같은 cpu로 스케쥴링 되어 재개되었을 수도 있다)
  • set_freepointer(s, object, c->freelist);
    • per cpu 캐시의 freelist에 insert할 준비를 하기 위해 object의 FP(Free Pointer)에 기존 per cpu 캐시 freelist 값(선두 object를 가리킴)을 기록한다.
  • if (unlikely(!this_cpu_cmpxchg_double( s->cpu_slab->freelist, s->cpu_slab->tid, c->freelist, tid, object, next_tid(tid)))) { note_cmpxchg_failure(“slab_free”, s, tid); goto redo; }
    • per cpu 캐시의 freelist에 해제할 object 그리고 tid에 다음 tid를 atomic하게 치환하는 것이 성공하지 못한 경우 redo 레이블로 다시 한다.
  • stat(s, FREE_FASTPATH);
    • object의 해제가 완료되었으므로 FREE_FASTPATH stat을 증가시킨다.
  • } else __slab_free(s, page, x, addr);
    • slub page가 현재 per cpu 캐시의 page에서 관리하지 않는 경우 slowpath 방식으로 object를 free 한다.


다음 그림은 object를 해제할 때 fastpath 루틴이 동작하여 현재의 per cpu 캐시의 freelist의 선두에 free object를 insert한 것을 보여준다.





static inline void slab_free_hook(struct kmem_cache *s, void *x)
        kmemleak_free_recursive(x, s->flags);

         * Trouble is that we may no longer disable interrupts in the fast path
         * So in order to make the debug calls that expect irqs to be
         * disabled we need to disable interrupts temporarily.
#if defined(CONFIG_KMEMCHECK) || defined(CONFIG_LOCKDEP)
                unsigned long flags;

                kmemcheck_slab_free(s, x, s->object_size);
                debug_check_no_locks_freed(x, s->object_size);
        if (!(s->flags & SLAB_DEBUG_OBJECTS))
                debug_check_no_obj_freed(x, s->object_size);

        kasan_slab_free(s, x);

slub object free 디버깅을 위해 object를 해제하기 전에 처리할 일을 수행한다.




 * Slow path handling. This may still be called frequently since objects
 * have a longer lifetime than the cpu slabs in most processing loads.
 * So we still attempt to reduce cache line usage. Just take the slab
 * lock and free the item. If there is no additional partial page
 * handling required then we can return immediately.
static void __slab_free(struct kmem_cache *s, struct page *page,
                        void *x, unsigned long addr)
        void *prior;
        void **object = (void *)x;
        int was_frozen;
        struct page new;
        unsigned long counters;
        struct kmem_cache_node *n = NULL;
        unsigned long uninitialized_var(flags);

        stat(s, FREE_SLOWPATH);

        if (kmem_cache_debug(s) &&
                !(n = free_debug_processing(s, page, x, addr, &flags)))

        do {
                if (unlikely(n)) {
                        spin_unlock_irqrestore(&n->list_lock, flags);
                        n = NULL;
                prior = page->freelist;
                counters = page->counters;
                set_freepointer(s, object, prior);
                new.counters = counters;
                was_frozen = new.frozen;
                if ((!new.inuse || !prior) && !was_frozen) {

                        if (kmem_cache_has_cpu_partial(s) && !prior) {

                                 * Slab was on no list before and will be
                                 * partially empty
                                 * We can defer the list move and instead
                                 * freeze it.
                                new.frozen = 1;

                        } else { /* Needs to be taken off a list */

                                n = get_node(s, page_to_nid(page));
                                 * Speculatively acquire the list_lock.
                                 * If the cmpxchg does not succeed then we may
                                 * drop the list_lock without any processing.
                                 * Otherwise the list_lock will synchronize with
                                 * other processors updating the list of slabs.
                                spin_lock_irqsave(&n->list_lock, flags);


        } while (!cmpxchg_double_slab(s, page,
                prior, counters,
                object, new.counters,
  • stat(s, FREE_SLOWPATH);
    • FREE_SLOWPATH stat을 증가시킨다.
  • if (kmem_cache_debug(s) && !(n = free_debug_processing(s, page, x, addr, &flags))) return;
    • SLAB_DEBUG_FLAGS 플래그를 사용한 경우 slub object free 디버깅을 위해 object를 해제하기 전에 체크하여 문제가 있는 경우 경고 메시지를 출력하여 알리고 처리를 중단하고 루틴을 빠져나간다.
  • if (unlikely(n)) { spin_unlock_irqrestore(&n->list_lock, flags); n = NULL; }
    • 낮은 확률로 lock이 걸려 있는 경우 걸어두었던 락을 해제하게 한다.
  • prior = page->freelist; counters = page->counters; set_freepointer(s, object, prior); new.counters = counters; was_frozen = new.frozen; new.inuse–;
    • page의 첫 free object 앞에 free object를 insert할 준비를 한다.
  • if ((!new.inuse || !prior) && !was_frozen) {
    • frozen된 페이지가 아니면서 모든 object가 다 사용 중이었거나 전부가 free object가 될 경우
      • frozen되지 않은 페이지는 kmem_cache에서 관리하지 않는 slub page이거나 per 노드에서 관리하는 slub page이다.
  •  if (kmem_cache_has_cpu_partial(s) && !prior) { new.frozen = 1;
    • per cpu 캐시에서 partial 리스트를 지원하면서 slub page에 free object가 없는 경우 frozen 시킬 준비를 한다.
      • per cpu 캐시가 관리하는 경우 frozen 시킨다.
        • frozen하는 경우 별도의 lock 없이 per cpu 캐시 page 또는 freelist에서 cmpxchg_double() 함수를 사용하여 atomic object의 연결 처리를 한다.
  • } else { n = get_node(s, page_to_nid(page)); spin_lock_irqsave(&n->list_lock, flags); }
    • per 노드에 대한 접근을 하기 위해 slub page에 해당하는 노드를 알아오고 spin lock을 한다.
  • } while (!cmpxchg_double_slab(s, page, prior, counters, object, new.counters, “__slab_free”));
    • page->freelist 선두에 해지할 object를 추가한다. 동시에 counter도 갱신하여 frozen과 inuse 값이 갱신되게 한다. 만일 이러한 변경이 atomic 하게 처리되지 않으면 다시 루프를 돌며 시도한다.


        if (likely(!n)) {

                 * If we just froze the page then put it onto the
                 * per cpu partial list.
                if (new.frozen && !was_frozen) {
                        put_cpu_partial(s, page, 1);
                        stat(s, CPU_PARTIAL_FREE);
                 * The list lock was not taken therefore no list
                 * activity can be necessary.
                if (was_frozen)
                        stat(s, FREE_FROZEN);

        if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
                goto slab_empty;

         * Objects left in the slab. If it was not on the partial list before
         * then add it.
        if (!kmem_cache_has_cpu_partial(s) && unlikely(!prior)) {
                if (kmem_cache_debug(s))
                        remove_full(s, n, page);
                add_partial(n, page, DEACTIVATE_TO_TAIL);
                stat(s, FREE_ADD_PARTIAL);
        spin_unlock_irqrestore(&n->list_lock, flags);

        if (prior) {
                 * Slab on the partial list.
                remove_partial(n, page);
                stat(s, FREE_REMOVE_PARTIAL);
        } else {
                /* Slab must be on the full list */
                remove_full(s, n, page);

        spin_unlock_irqrestore(&n->list_lock, flags);
        stat(s, FREE_SLAB);
        discard_slab(s, page);
  • if (likely(!n)) {
    • per 노드에 대한 접근이 필요 없는 경우
      • 즉 slub page가 하나의 free object만 있는 상태로 frozen 상태가 된 경우
  • if (new.frozen && !was_frozen) { put_cpu_partial(s, page, 1); stat(s, CPU_PARTIAL_FREE); }
    • kmem_cache에서 관리하지 않는 slub page의 object가 free 요청을 한 경우 frozen하여 per cpu 캐시의 partial 리스트에 추가하고 CPU_PARTIAL_FREE stat을 증가시킨다.
  • if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) goto slab_empty;
    • 낮은 확률로 slub page의 모든 object가 free object가 된 경우이면서 노드의 partial slub 수가 캐시의 최소 partial slub 수를 넘어가는 경우 slab_empty: 레이블로 이동한다.
      • per 노드의 partial 리스트에 있는 slub page의 모든 object가 free object 상태가 되었고, per 노드의 partial 리스트의 보관 slot을 초과한 경우
  • if (!kmem_cache_has_cpu_partial(s) && unlikely(!prior)) {
    • per cpu 캐시에서 partial 리스트가 지원되지 않으면서 낮은 확률로 free object가 없었던 경우
      • per cpu 캐시의 page에 free object가 하나 밖에 없는 slub page를 per 노드 partial 리스트로 보낼 조건을 비교한다.
  • if (kmem_cache_debug(s)) remove_full(s, n, page);
    • SLUB 디버깅 관련 생략
  • add_partial(n, page, DEACTIVATE_TO_TAIL); stat(s, FREE_ADD_PARTIAL); }
    • per 노드의 partial 리스트의 마지막에 slub page를 추가하고 FREE_ADD_PARTIAL stat을 증가시킨다.
  • spin_unlock_irqrestore(&n->list_lock, flags); return;
    • spin unlock을 수행 후 루틴을 빠져나간다.
  • slab_empty:
    • free object로만 이루어진 slab page를 버디 시스템으로 보내기 위해 이동해 올 레이블이다.
      • 사용중인 object가 없는 상태이다.
  • if (prior) { remove_partial(n, page); stat(s, FREE_REMOVE_PARTIAL);
    • free object가 있었으면 per 노드의 partial 리스트에서 제거한 후 FREE_REMOVE_PARTIAL stat을 증가시킨다.
  • } else { remove_full(s, n, page); }
    • free object가 하나도 없었으면 SLUB 디버깅 중에 연결되어 있던 full 리스트에서 제거한다
  • spin_unlock_irqrestore(&n->list_lock, flags); stat(s, FREE_SLAB); discard_slab(s, page);
    • spin unlock을 수행 후 FREE_SLAB stat을 증가시키고, slub page를 버디 시스템으로 다시 돌려준다.


다음 그림은 slub object를 Slowpath 단계에서 처리하는 방법을 보여준다.




 * Put a page that was just frozen (in __slab_free) into a partial page
 * slot if available. This is done without interrupts disabled and without
 * preemption disabled. The cmpxchg is racy and may put the partial page
 * onto a random cpus partial slot.
 * If we did not find a slot then simply move all the partials to the
 * per node partial list.
static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
        struct page *oldpage;
        int pages;
        int pobjects;

        do {
                pages = 0;
                pobjects = 0;
                oldpage = this_cpu_read(s->cpu_slab->partial);

                if (oldpage) {
                        pobjects = oldpage->pobjects;
                        pages = oldpage->pages;
                        if (drain && pobjects > s->cpu_partial) {
                                unsigned long flags;
                                 * partial array is full. Move the existing
                                 * set to the per node partial list.
                                unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));
                                oldpage = NULL;
                                pobjects = 0;
                                pages = 0; 
                                stat(s, CPU_PARTIAL_DRAIN);

                pobjects += page->objects - page->inuse;

                page->pages = pages;
                page->pobjects = pobjects;
                page->next = oldpage;

        } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page)
                                                                != oldpage);
        if (unlikely(!s->cpu_partial)) {
                unsigned long flags;

                unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));

지정한 slub page를 per cpu 캐시의 partial 리스트의 선두에 추가한다. 단 인수로 drain이 허용하는 경우 per cpu 캐시의 partial 리스트가 overflow 될 경우 기존에 있던 slub page들을 모두 per 노드의 partial 리스트로 이동시킨다.

  • __free_slab() 함수에서 object 해제 요청 시 kmem_cache가 관리하지 않던 slub 페이지가 새롭게 partial 리스트로 진입하는 경우 drain=1이 요청된다.


  • oldpage = this_cpu_read(s->cpu_slab->partial);
    • per cpu 캐시의 partial 리스트의 선두 페이지
  • pobjects = oldpage->pobjects;
    • 선두 페이지에 있던 free object 수
  • pages = oldpage->pages;
    • 자신을 포함하여 뒤(next)로 연결되어 있는 slub page들의 수


인수 drain 설정이 true이면서 free object의 수가 per cpu 캐시 partial 리스트에서 관리하는 제한 object 수를 넘긴 경우 per cpu 캐시의 partial 리스트에 있는 모든 slub page에 대해 per 노드의 partial 리스트로 옮긴다.

  • if (drain && pobjects > s->cpu_partial) {
    • 인수 drain 설정이 true이면서 free object의 수가 per cpu 캐시 partial 리스트에서 관리하는 제한 object 수(s->cpu_partial)를 넘긴 경우
  • unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));
    • 모든 slub page에 대해 per 노드의 partial 리스트로 옮긴다.
  • oldpage = NULL; pobjects = 0; pages = 0; stat(s, CPU_PARTIAL_DRAIN);
    • per cpu 캐시의 partial 리스트의 관리 변수들을 0으로 초기화하고 CPU_PARTIAL_DRAIN stat을 증가시킨다.


slub 페이지를 per cpu 캐시의 partial 리스트에 추가한다.

  • pages++; pobjects += page->objects – page->inuse;
    • 페이지 수를 증가시키고 현재 slub page의 free object 수를 pobjects에 더한다.
      • pobjects
        • 정확하지는 않지만 대략적으로 내 slub page를 포함한 뒤의 slub page들의 총 free object 수가 담긴다.
        • 이 카운터는 종종 free 되는 object들로 인해 정확히 산출되지 않는다.
  • page->pages = pages; page->pobjects = pobjects; page->next = oldpage;
    • page의 pages, pobjects를 update하고 next 멤버 변수에 첫 slub page를 대입하여 선두에 slub page를 insert 할 준비를 한다.
  • } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page) != oldpage);
    • atomic operation으로 per cpu 캐시의 partial 리스트의 선두에 slub page를 insert한다.


per cpu 캐시의 partial 리스트에서 관리하는 제한 object 수가 0으로 설정된 경우 per cpu 캐시의 partial 리스트에 있는 모든 slub page들을 per 노드의 partial 리스트로 옮긴다

  • if (unlikely(!s->cpu_partial)) { unsigned long flags; local_irq_save(flags); unfreeze_partials(s, this_cpu_ptr(s->cpu_slab)); local_irq_restore(flags); }
    • 적은 확률로 per cpu 캐시의 partial 리스트에서 관리하는 제한 object 수(cpu_partial)가 0으로 설정된 경우 per cpu 캐시의 partial 리스트에 있는 모든 slub page들을 per 노드의 partial 리스트로 옮긴다.


다음 그림은 slub page를 per cpu 캐시의 partial 리스트의 선두에 추가하는 것을 보여준다.



static inline void add_partial(struct kmem_cache_node *n,
                                struct page *page, int tail)
        __add_partial(n, page, tail);

지정된 slub page를 per 노드의 partial 리스트의 지정된 위치(선두 또는 후미)에 추가한다.




 * Management of partially allocated slabs.
static inline void
__add_partial(struct kmem_cache_node *n, struct page *page, int tail)
        if (tail == DEACTIVATE_TO_TAIL)
                list_add_tail(&page->lru, &n->partial);
                list_add(&page->lru, &n->partial);

지정된 slub page를 per 노드의 partial 리스트의 지정된 위치(선두 또는 후미)에 추가하고 n->nr_partial을 증가 시킨다.


다음 그림은 slub page를 per 노드의 partial 리스트의 지정된 위치(선두 또는 후미)에 추가하는 모습을 보여준다.





static inline void remove_partial(struct kmem_cache_node *n,
                                        struct page *page)
        __remove_partial(n, page);

지정된 slub page를 per 노드의 partial 리스트에서 제거한다.




static inline void
__remove_partial(struct kmem_cache_node *n, struct page *page)

지정된 slub page를 per 노드의 partial 리스트에서 제거하고 n->nr_partial 을 감소시킨다.


다음 그림은 per 노드의 partial 리스트에서 제거하여 kmem_cache가 관리하지 않는 상태로 바꾼다.





 * Unfreeze all the cpu partial slabs.
 * This function must be called with interrupts disabled
 * for the cpu using c (or some other guarantee must be there
 * to guarantee no concurrent accesses).
static void unfreeze_partials(struct kmem_cache *s,
                struct kmem_cache_cpu *c)
        struct kmem_cache_node *n = NULL, *n2 = NULL;
        struct page *page, *discard_page = NULL;

        while ((page = c->partial)) {
                struct page new;
                struct page old;

                c->partial = page->next;

                n2 = get_node(s, page_to_nid(page));
                if (n != n2) {
                        if (n)

                        n = n2;

                do {

                        old.freelist = page->freelist;
                        old.counters = page->counters;

                        new.counters = old.counters;
                        new.freelist = old.freelist;

                        new.frozen = 0;

                } while (!__cmpxchg_double_slab(s, page,
                                old.freelist, old.counters,
                                new.freelist, new.counters,
                                "unfreezing slab"));

                if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) {
                        page->next = discard_page;
                        discard_page = page;
                } else {
                        add_partial(n, page, DEACTIVATE_TO_TAIL);
                        stat(s, FREE_ADD_PARTIAL);

        if (n)

        while (discard_page) {
                page = discard_page;
                discard_page = discard_page->next;

                stat(s, DEACTIVATE_EMPTY);
                discard_slab(s, page);
                stat(s, FREE_SLAB);

per cpu 캐시의 partial 리스트에서 관리하는 모든 slub page들을 per 노드의 partial 리스트의 후미에 추가한다. 만일 per 노드의 partial 리스트가 초과되는 경우 overflow된 slub page들 중 할당된 object가 없는 slub page를 버디 시스템으로 되돌려 준다.


다음 그림은 per cpu 캐시의 partial 리스트의 모든 slub page들을 per 노드의 partial 리스트로 옮기는 과정을 보여준다.





static void discard_slab(struct kmem_cache *s, struct page *page)
        dec_slabs_node(s, page_to_nid(page), page->objects);
        free_slab(s, page);

per 노드의 nr_slabs(slab page 갯수)를 감소시키고, per 노드의 total_objects 값도 objects 값 만큼 뺀다.  그런 후 slub page를 해제하여 버디 시스템으로 돌려놓는다.




static inline void dec_slabs_node(struct kmem_cache *s, int node, int objects)
        struct kmem_cache_node *n = get_node(s, node);

        atomic_long_sub(objects, &n->total_objects);

per 노드의 nr_slabs(slab page 갯수)를 감소시키고, per 노드의 total_objects 값도 objects 값 만큼 뺀다.



댓글 남기기

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