Slub Memory Allocator -3- (order 계산)

calculate_alignment()

mm/slab_common.c

/*
 * Figure out what the alignment of the objects will be given a set of
 * flags, a user specified alignment and the size of the objects.
 */
unsigned long calculate_alignment(unsigned long flags,
                unsigned long align, unsigned long size)
{
        /*
         * If the user wants hardware cache aligned objects then follow that
         * suggestion if the object is sufficiently large.
         *
         * The hardware cache alignment cannot override the specified
         * alignment though. If that is greater then use it.
         */
        if (flags & SLAB_HWCACHE_ALIGN) {
                unsigned long ralign = cache_line_size();
                while (size <= ralign / 2)
                        ralign /= 2;
                align = max(align, ralign);
        }

        if (align < ARCH_SLAB_MINALIGN)
                align = ARCH_SLAB_MINALIGN;

        return ALIGN(align, sizeof(void *));
}

지정한 객체에 대한 인수 size와 align을 산정한다. 만일 SLAB_HWCACHE_ALIGN 플래그를 사용하여 하드웨어 캐시 정렬 요청을 하는 경우 그에 맞게 최종 align을 구한다.

  • rpi2:
    • size=0~8
      • s->align=8
    • size=9~16
      • s->align=16
    • size=17~32
      • s->align=32
    • size=33~64
      • s->align=64
    • size=65~
      • size 값을 4 단위로 round up
      • 68, 72, 76, 80, …
  • if (flags & SLAB_HWCACHE_ALIGN) {
    • slab에 대해 하드웨어 캐시 정렬 요청이 있는 경우
  • unsigned long ralign = cache_line_size();
    • CONFIG_ARCH_HAS_CACHE_LINE_SIZE 커널 옵션이 제공되지 않는 경우 default로 L1_CACHE_BYTES이 사용된다.
      • rpi2: 64 bytes
  • while (size <= ralign / 2) ralign /= 2;
    • size가 ralign 값의 절반 이하인 경우 ralign을 절반씩 줄여나간다. (…, 64, 32, 16, 8)
      • 예) size=30, ralign=64
        • ralign=32
  • align = max(align, ralign);
    • 요청한 align과 hwcache에 맞춰 산출된 ralign 중 가장 큰 수로 align을 사용한다.
  • if (align < ARCH_SLAB_MINALIGN) align = ARCH_SLAB_MINALIGN;
    • align이 최소 8 이상이 되도록 조정한다.
    • ARCH_SLAB_MINALIGN
      • CONFIG_EABI를 사용하며 ARMv5 이상의 아키텍처는 8이다.
  • return ALIGN(align, sizeof(void *));
    • 리턴되는 align 값은 워드 단위로 round up한다.
      • 32bit arm 예) align=66
        • return 68;

 

calculate_sizes()

mm/slub.c

/*
 * calculate_sizes() determines the order and the distribution of data within
 * a slab object.
 */
static int calculate_sizes(struct kmem_cache *s, int forced_order)
{
        unsigned long flags = s->flags;
        unsigned long size = s->object_size;
        int order;

        /*
         * Round up object size to the next word boundary. We can only
         * place the free pointer at word boundaries and this determines
         * the possible location of the free pointer.
         */
        size = ALIGN(size, sizeof(void *));

#ifdef CONFIG_SLUB_DEBUG
        /*
         * Determine if we can poison the object itself. If the user of
         * the slab may touch the object after free or before allocation
         * then we should never poison the object itself.
         */
        if ((flags & SLAB_POISON) && !(flags & SLAB_DESTROY_BY_RCU) &&
                        !s->ctor)
                s->flags |= __OBJECT_POISON;
        else
                s->flags &= ~__OBJECT_POISON;


        /*
         * If we are Redzoning then check if there is some space between the
         * end of the object and the free pointer. If not then add an
         * additional word to have some bytes to store Redzone information.
         */
        if ((flags & SLAB_RED_ZONE) && size == s->object_size)
                size += sizeof(void *);
#endif

        /*
         * With that we have determined the number of bytes in actual use
         * by the object. This is the potential offset to the free pointer.
         */
        s->inuse = size;

        if (((flags & (SLAB_DESTROY_BY_RCU | SLAB_POISON)) ||
                s->ctor)) {
                /*
                 * Relocate free pointer after the object if it is not
                 * permitted to overwrite the first word of the object on
                 * kmem_cache_free.
                 *
                 * This is the case if we do RCU, have a constructor or
                 * destructor or are poisoning the objects.
                 */
                s->offset = size;
                size += sizeof(void *);
        }

지정된 forced_order 또는 객체 사이즈(s->size)로 적절히 산출된 order 둘 중 하나를 선택하여 slab에 들어갈 최소 객체 수(s->min), 적절한 객체 수(s->oo) 및 최대 객체 수(s->max)를 설정하고 1을 반환한다. 객체 수가 0인 경우 에러로 0을 반환한다.

  • size = ALIGN(size, sizeof(void *));
    • size를 포인터 사이즈 단위로 round up 한다.
  • if (((flags & (SLAB_DESTROY_BY_RCU | SLAB_POISON)) || s->ctor)) { s->offset = size; size += sizeof(void *); }
    • flags에 SLAB_DESTROY_BY_RCU 또는 SLAB_POISON이 있거나 생성자 함수가 설정된 경우 FP(Free Pointer)위치를 뒤로 옮기기 위해 s->offset=size를 대입하고 size에 포인터 사이즈가 추가된다.
#ifdef CONFIG_SLUB_DEBUG
        if (flags & SLAB_STORE_USER)
                /*
                 * Need to store information about allocs and frees after
                 * the object.
                 */
                size += 2 * sizeof(struct track);

        if (flags & SLAB_RED_ZONE)
                /*
                 * Add some empty padding so that we can catch
                 * overwrites from earlier objects rather than let
                 * tracking information or the free pointer be
                 * corrupted if a user writes before the start
                 * of the object.
                 */
                size += sizeof(void *);
#endif

        /*
         * SLUB stores one object immediately after another beginning from
         * offset 0. In order to align the objects we have to simply size
         * each object to conform to the alignment.
         */
        size = ALIGN(size, s->align);
        s->size = size;
        if (forced_order >= 0)
                order = forced_order;
        else
                order = calculate_order(size, s->reserved);

        if (order < 0)
                return 0;

        s->allocflags = 0;
        if (order)
                s->allocflags |= __GFP_COMP;

        if (s->flags & SLAB_CACHE_DMA)
                s->allocflags |= GFP_DMA;

        if (s->flags & SLAB_RECLAIM_ACCOUNT)
                s->allocflags |= __GFP_RECLAIMABLE;

        /*
         * Determine the number of objects per slab
         */
        s->oo = oo_make(order, size, s->reserved);
        s->min = oo_make(get_order(size), size, s->reserved);
        if (oo_objects(s->oo) > oo_objects(s->max))
                s->max = s->oo;

        return !!oo_objects(s->oo);
}
  • if (flags & SLAB_STORE_USER) size += 2 * sizeof(struct track);
    • 디버그 정보가 포함된 object에서 SLAB_STORE_USER GFP 플래그가 사용된 경우 track 구조체의 2배만큼의 사이즈를 추가한다.
  • if (flags & SLAB_RED_ZONE) size += sizeof(void *);
    • 디버그 정보가 포함된 object에서 SLAB_RED_ZONE GFP 플래그가 사용된 경우 포인터 사이즈를 추가한다.
  • size = ALIGN(size, s->align);
    • size를 s->align 단위로 round up한다.
  • if (forced_order >= 0) order = forced_order;
    • forced_order가 0 이상으로 설정된 경우 forced_order를 사용한다.
  •  else order = calculate_order(size, s->reserved);
    • forced_order가 설정되지 않은 경우(-1) order를 계산한다.
  • if (order < 0) return 0;
    • 계산된 order가 0보다 작으면 처리를 포기하고 함수를 빠져나간다.
  • if (order) s->allocflags |= __GFP_COMP;
    • order가 0이 아닌 경우 compound 페이지 플래그를 추가한다.
  • if (s->flags & SLAB_CACHE_DMA) s->allocflags |= GFP_DMA;
    • SLAB_CACHE_DMA 플래그가 요청된 경우 s->allocflags에 GFP_DMA 플래그를 추가하여 ZONE_DMA 영역에서 할당 요청을 한다.
  • if (s->flags & SLAB_RECLAIM_ACCOUNT) s->allocflags |= __GFP_RECLAIMABLE;
    • SLAB_RECLAIM_ACCOUNT 플래그가 요청된 경우 s->allocflags에 페이지 할당 시 migrate type을 reclaimable로 하여 메모리 부족 시 회수가 가능한 페이지 속성으로 할당 요청을 한다.
  • s->oo = oo_make(order, size, s->reserved);
    • unused 영역을 최소화 시키기 위해 적절히 산출된 order 페이지에 포함되는 객체 수와 order 값이 포함된 kmem_cache_order_objects 구조체 객체에 담아 s->oo에 대입한다.
  • s->min = oo_make(get_order(size), size, s->reserved);
    • 최소 영역으로 산출된 order 페이지에 포함되는 객체 수와 order 값이 포함된 kmem_cache_order_objects 구조체 객체에 담아 s->min에 대입한다
  • if (oo_objects(s->oo) > oo_objects(s->max)) s->max = s->oo;
    • s->oo에 담긴 객체 수가 s->max에 담긴 객체 수보다 큰 경우 s->max 값을 갱신한다.
  • return !!oo_objects(s->oo);
    • s->oo에 담긴 객체 수가 1개 이상인 경우 1을 반환한다. 그렇지 않으면 0을 반환한다.

다음 그림은 slab에 사용할 최소 order와 적절한 order 및 최대 order가 산출된 모습을 보여준다.

calculate_sizes-1a

  • object에 메타데이터가 없는 경우 s->inuse는 0이지만, 메타데이터가 포함되어야 하는 경우 s->inuse는 s->object_size 값으로 설정된다.
    • inuse(메타데이터를 가리키는 offset)

 

calculate_order()

mm/slub.c

static inline int calculate_order(int size, int reserved)
{
        int order;
        int min_objects;
        int fraction;
        int max_objects;

        /*
         * Attempt to find best configuration for a slab. This
         * works by first attempting to generate a layout with
         * the best configuration and backing off gradually.
         *
         * First we reduce the acceptable waste in a slab. Then
         * we reduce the minimum objects required in a slab.
         */
        min_objects = slub_min_objects;
        if (!min_objects)
                min_objects = 4 * (fls(nr_cpu_ids) + 1);
        max_objects = order_objects(slub_max_order, size, reserved);
        min_objects = min(min_objects, max_objects);

        while (min_objects > 1) {
                fraction = 16;
                while (fraction >= 4) {
                        order = slab_order(size, min_objects,
                                        slub_max_order, fraction, reserved);
                        if (order <= slub_max_order)
                                return order;
                        fraction /= 2;
                }
                min_objects--;
        }

        /*
         * We were unable to place multiple objects in a slab. Now
         * lets see if we can place a single object there.
         */
        order = slab_order(size, 1, slub_max_order, 1, reserved);
        if (order <= slub_max_order)
                return order;

        /*
         * Doh this slab cannot be placed using slub_max_order.
         */
        order = slab_order(size, 1, MAX_ORDER, 1, reserved);
        if (order < MAX_ORDER)
                return order;
        return -ENOSYS;
}

slub 할당을 위해 필요한 적절한 order를 산출한다.

  • 산출된 order 페이지는 적어도 1개 이상의 객체 수와 reserve 영역을 포함되며 사용할 수 없는 unused 영역이 발생하는 경우 포함된다.
  • 객체 사이즈가 큰 경우 unused 영역이 커질 가능성이 커진다. 이러한 unused 영역이 slab 영역의 일정 부분 이상으로 크면 영역이 낭비된다고 판단하여 min_objects와 fraction을 변경하며 order를 산출하여 unused 영역이 작을 때의 order를 사용하게 된다.
  •  min_objects = slub_min_objects;
    • “slub_min_order=” 커널 파라메터로 설정된 값을 대입한다.
      • default=0
  • if (!min_objects) min_objects = 4 * (fls(nr_cpu_ids) + 1);
    • slab에서 사용할 최소 객체 수는 cpu 수에 비례한다.
      • rpi2 예)
        • min_objects=4 * (3 + 1) = 16
  • max_objects = order_objects(slub_max_order, size, reserved);
    • 요청된 최대 order 페이지에서  reserve 영역을 제외한 영역에서 생성할 수 있는 객체 수를 구한다.
  • min_objects = min(min_objects, max_objects);
    • min_objects가 max_objects보다 큰 경우 min_objects에 max_objects를 대입한다.

1st phase:

1차 루프로 산출된 min_objects에서 2까지 줄여가고, 2차 루프로 fraction을 16, 8, 4와 같이 줄여가며 order 산출을 시도하여 결과가 slub_max_order 이하인 경우 산출한 order가 적절하다고 판단하여 그 값을 반환한다.

  • while (min_objects > 1) {
    • 산출된 min_objects가 1을 초과하는 경우 루프를 돈다.
      • min_objects가 16으로 산출된 경우 예) 16, 15, 14, … 2까지 루프를 돈다.
  • fraction = 16;
    • unused 영역과 slab 사이즈를 16으로 나눈 영역의 크기를 서로 비교하기 위해 먼저 fraction을 16으로 설정한다.
  • while (fraction >= 4) {
    • fraction이 4이상인 경우에 한해 루프를 돈다.
      • 16, 8, 4와 같이 총 3회 루프를 수행한다.
  • order = slab_order(size, min_objects, slub_max_order, fraction, reserved);
    • slab 생성을 위해 지정된 최소 객체 수 이상을 할당하는데 필요한 적절한 order를 산출한다.
    • min_objects와 fraction 변수가 바뀌면서 수행된다.
  • if (order <= slub_max_order) return order;
    • 산출된 order가 slub_max_order 이하인 경우 적절하다고 판단하여 해당 order 값을 리턴한다.
      • slub_max_oder
        • default=3이고 “slub_max_order=” 커널 파라메터로 변경될 수 있다.
  • fraction /= 2;
    • fraction을 반으로 줄이고 2차 루프를 계속 수행한다.
  • min_objects–;
    • min_objects를 1 줄이고 1차 루프를 계속 수행한다.

2nd phase

  • order = slab_order(size, 1, slub_max_order, 1, reserved); if (order <= slub_max_order) return order;
    • min_objects를 1로, fraction을 1로 변경하고 다시 order를 산출하여 결과가 slub_max_order 이하인 경우 적절하다고 판단하여 해당 order 값을 리턴한다.

3rd phase

  • order = slab_order(size, 1, MAX_ORDER, 1, reserved); if (order < MAX_ORDER) return order;
    • 2nd phase에 추가로 slub_max_order 값이 아닌 MAX_ORDER로 상승시키고 다시 order를 산출하여 결과가 slub_max_order 이하인 경우 적절하다고 판단하여 해당 order 값을 리턴한다.

다음 그림은 slab 할당을 위해 적절한 order를 산출하는 모습을 보여준다.

calculate_order-1b

 

order_objects()

mm/slub.c

static inline int order_objects(int order, unsigned long size, int reserved)
{
        return ((PAGE_SIZE << order) - reserved) / size;
}

요청된 order 페이지에서  reserve 영역을 제외한 영역에서 생성할 수 있는 객체 수를 구한다.

  • 객체가 할당되는 2^order 페이지에서 reserve 영역을 제외한 영역을 size로 나눈 수를 반환한다.

다음 그림은 order 만큼의 페이지의 reserve 영역을 제외한 크기에서 생성할 수 있는 object의 수를 알아오는 것을 보여준다.

order_objects-1b

 

slab_order()

mm/slub.c

static inline int slab_order(int size, int min_objects,
                                int max_order, int fract_leftover, int reserved)
{
        int order;
        int rem;
        int min_order = slub_min_order;

        if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE)
                return get_order(size * MAX_OBJS_PER_PAGE) - 1;

        for (order = max(min_order,
                                fls(min_objects * size - 1) - PAGE_SHIFT);
                        order <= max_order; order++) {

                unsigned long slab_size = PAGE_SIZE << order;

                if (slab_size < min_objects * size + reserved)
                        continue;

                rem = (slab_size - reserved) % size;

                if (rem <= slab_size / fract_leftover)
                        break;

        }

        return order;
}

slab 생성을 위해 지정된 최소 객체 수 이상을 할당하는데 필요한 적절한 order를 산출한다.

  •  보통 0-order를 많이 선호하는데 큰 사이즈의 객체를 사용하는 경우 남는 공간을 낭비하지 않기 위해 더 높은 order를 사용한다.
  • if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE) return get_order(size * MAX_OBJS_PER_PAGE) – 1;
    • size로 적절한 order를 얻어온 값이 MAX_OBJS_PER_PAGE(32767)를 초과하는 경우 size * MAX_OBJS_PER_PAGE(32767)를 처리할 수 있는 order 값 – 1을 반환한다.
  • for (order = max(min_order, fls(min_objects * size – 1) – PAGE_SHIFT); order <= max_order; order++) {
    • 최소 order 부터 최대 order 까지 루프를 돌며 적절한 order를 찾을 때 까지 루프를 돈다.
      • 최소 order
        • 인수로 지정한 min_order와 최소 객체 수를 반영할 수 있는 order 둘 중 작은 order 값으로 한다.
  •  unsigned long slab_size = PAGE_SIZE << order;
    • slab 사이즈 영역을 2^order 페이지 값으로 시도한다.
  • if (slab_size < min_objects * size + reserved) continue;
    • slab 사이즈 영역이 객체가 사용할 최소 공간보다 작은 경우 order를 높여서 다시 시도한다.
  • rem = (slab_size – reserved) % size;
    • slab 사이즈 영역에서 사용할 수 없게되는 나머지 영역 크기 rem을 구한다.
      • slab 영역에서 reserved 영역을 뺀 나머지 영역을 객체 사이즈로 나눈 나머지
  • rem이 slab_size를 fract_leftover로 나눈 몫 이하인 경우 적절한 order로 판단되어 해당 order를 결정한다.

slab_order-1b

 

get_order()

include/asm-generic/getorder.h

/**
 * get_order - Determine the allocation order of a memory size
 * @size: The size for which to get the order
 *
 * Determine the allocation order of a particular sized block of memory.  This
 * is on a logarithmic scale, where:
 *
 *      0 -> 2^0 * PAGE_SIZE and below
 *      1 -> 2^1 * PAGE_SIZE to 2^0 * PAGE_SIZE + 1
 *      2 -> 2^2 * PAGE_SIZE to 2^1 * PAGE_SIZE + 1
 *      3 -> 2^3 * PAGE_SIZE to 2^2 * PAGE_SIZE + 1
 *      4 -> 2^4 * PAGE_SIZE to 2^3 * PAGE_SIZE + 1
 *      ...
 *
 * The order returned is used to find the smallest allocation granule required
 * to hold an object of the specified size. 
 *
 * The result is undefined if the size is 0.
 *
 * This function may be used to initialise variables with compile time
 * evaluations of constants.
 */
#define get_order(n)                                            \
(                                                               \
        __builtin_constant_p(n) ? (                             \
                ((n) == 0UL) ? BITS_PER_LONG - PAGE_SHIFT :     \
                (((n) < (1UL << PAGE_SHIFT)) ? 0 :              \
                 ilog2((n) - 1) - PAGE_SHIFT + 1)               \
        ) :                                                     \
        __get_order(n)                                          \
)

n 값을 버디 시스템의 order로 표현할 때의 값을 구한다.

  • 예) n=1025 ~ 2048
    • -> 1

 

__get_order()

include/asm-generic/getorder.h

/*
 * Runtime evaluation of get_order()
 */
static inline __attribute_const__
int __get_order(unsigned long size)
{
        int order;

        size--;
        size >>= PAGE_SHIFT;
#if BITS_PER_LONG == 32
        order = fls(size);
#else
        order = fls64(size);
#endif
        return order;
}

size를 버디 시스템의 order로 표현할 때의 값을 구한다.

  • size에서 1을 뺀 값을 페이지 수로 변경하고 이를 표현할 수 있는 필요 비트 수를 구한다.
    • fls()
      • lsb -> msb로 검색하여 가장 마지막에 발견되는 1로된 비트 번호 + 1
        • 예) 0xf000_0000 -> 32
  • 예) size=0x10_0000 (1MB)
    • -> 8

 

oo_make()

mm/slub.c

static inline struct kmem_cache_order_objects oo_make(int order,
                unsigned long size, int reserved)
{
        struct kmem_cache_order_objects x = {
                (order << OO_SHIFT) + order_objects(order, size, reserved)
        };

        return x;
}

order, size 및 reserved를 사용하여 산출한 객체 수와 order 값을 kmem_cache_order_objects 구조체 객체에 담고 그 값을 반환한다.

  • 객체는 하나의 unsigned long 값을 사용하는데 lsb 16bit에 객체 수를 담고 나머지 bit에 order 값을 담는다.
  • OO_SHIFT=16

아래 그림은 oo_make() 인라인 함수를 사용하여 order 값과 산출된 객체 수를 kmem_cache_order_objects라는 내부 규조체 객체에 담아 반환을 하는 모습을 보여준다.

oo_make-1

 

oo_objects()

mm/slub.c

static inline int oo_objects(struct kmem_cache_order_objects x)
{
        return x.x & OO_MASK;
}

x 값에서 객체 수 값 만을 반환한다.

  • x 값을 65535 (0xFFFF)로 마스크하여 order 값을 제거하고 객체 수 값만을 반환한다.

다음 그림은  kmem_cache_order_objects 구조체 객체에서 객체 수 값만을 반환받는 모습을 보여준다.

oo_objects-1

참고

답글 남기기

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