· KLDP.org · KLDP.net · KLDP Wiki · KLDP BBS ·
Slab Allocator(½½·¦ ÇÒ´çÀÚ)

Slab Allocator(½½·¦ ÇÒ´çÀÚ)

  • ÀÛ¼ºÀÚ
    Á¶ÀçÇõ(Mminzkn@minzkn.com)

  • °íÄ£°úÁ¤
    2008³â 12¿ù 13ÀÏ : ±è±â¿À(gurugio)¾¾ÀÇ Offline study °³Áø 2008³â 12¿ù 15ÀÏ : óÀ½¾¸ 2009³â 3¿ù 5ÀÏ : slabÃʱâÈ­½Ã¿¡ »ç¿ë°¡´ÉÇÑ object¼ö¸¦ °è»êÇÏ´Â ¹æ¹ý º¯°æÇÏ¿© ¼Ò°³

ÀбâÀü¿¡

¿©±â¼­ ³ª¿À´Â ¿ë¾î ¹× º¯¼ö¸íµîÀº ½ÇÁ¦ ¹ü¿ëÀûÀÎ ÀÌ·ÐÃ¥¿¡ ³ª¿Â ¿ë¾îÇؼ®°ú ´Ù¸¦¼öµµ ÀÖ½À´Ï´Ù. ¶ÇÇÑ ¾Ë°í¸®ÁòÀÇ ±âº»À» °­Á¶ÇÏ°í ÀÌÇصµ¸¦ ³ôÀ̱â À§ÇÏ¿© ½ÇÁ¦ º¸°­µÇ¾î¾ß ÇҺκеéÀÌ Á¦°ÅµÇ¾î ¼Ò°³µË´Ï´Ù.

À¯·¡ ¹× Ư¡

Slab Allocator(½½·¦ ÇÒ´çÀÚ)´Â 1994³â Sun MicrosystemsÀÇ Solaris 2.4¶ó´Â ¿î¿µÃ¼Á¦¿¡¼­ ±¸ÇöµÈ "Slab allocator"¶ó´Â ÇÒ´çÀü·«¿¡¼­ À¯·¡µÇ¾ú½À´Ï´Ù.

ÀÌ ÇÒ´çÀü·«ÀÇ ÁÖ¿ä Ư¡À¸·Î´Â ´ÙÀ½°ú °°Àº Á¡ÀÌ ÀÖ½À´Ï´Ù.

  1. À¯Áö¿¡ ÇÊ¿äÇÑ ÀڷᱸÁ¶¿Í ÇÔ²² »ý¼ºÀÚ(Constructor), ¼Ò¸êÀÚ(Destructor)¸¦ ±¸ÇöÇÔÀ¸·Î½á ÀÏÁ¾ÀÇ °´Ã¼·Î¼­ÀÇ Á¢±ÙÀ» ±¸ÇöÇÕ´Ï´Ù. (ÇÏÁö¸¸ ÀϺΠ¿î¿µÃ¼Á¦¿¡¼­´Â °´Ã¼°üÁ¡À¸·Î ¹Ù¶óº¸±â´Â ÇÏÁö¸¸ »ý¼ºÀÚ, ¼Ò¸êÀÚ¸¦ »ç¿ëÇÏÁö ¾Ê´Â °æ¿ìµµ ¸¹ÀÌ ÀÖ½À´Ï´Ù.)
  2. °´Ã¼¸¦ ºÒÇÊ¿äÇÏ°Ô ¹Ýº¹ ÃʱâÈ­ ÇÏ´Â Çö»óÀ» ȸÇÇÇϱâ À§ÇÏ¿© ÇÒ´çÈÄ¿¡ ÇØÁ¦µÇ´Â °´Ã¼¸¦ Áï°¢ Æó±âÇÏÁö ¾Ê°í ¸Þ¸ð¸®¿¡ ±×´ë·Î À¯ÁöÇÏ·Á´Â ¼Ó¼ºÀ» °¡Áö°í ÀÖ½À´Ï´Ù.
  3. ºñ½ÁÇÑ Å©±âÀÇ °´Ã¼¸¦ ij½ÃÇÏ´Â À¯»ç±¸Á¶¸¦ »ç¿ëÇϱ⠶§¹®¿¡ ÀϹÝÀûÀ¸·Î ¹ß»ýÇÒ¼ö ÀÖ´Â ´ÜÆíÈ­ ¹®Á¦¸¦ ÇؼÒÇÕ´Ï´Ù.
  4. ¸®´ª½ºÀÇ °æ¿ì Ä¿³Î¿¡¼­ »ç¿ëÇÏ´Â ÀÏ·ÃÀÇ ±¸Á¶Áß¿¡ ¸Å¿ì ºóµµ°¡ ³ôÀº ¹Ýº¹ÇҴ簴ü¿¡ ´ëÇؼ­ Cache·Î ¹Ù¶óº¸°í ±×¿¡ ¸Âµµ·Ï SlabÀ» ±¸ÇöÇÕ´Ï´Ù.
  5. Çϵå¿þ¾î ij½Ã¿¡ Á¤·ÄµÉ¼ö ÀÖ°í Ä÷¯¸µ±â¹ýÀÌ Àû¿ëµÇ±â ¶§¹®¿¡ ij½Ã¼º´ÉÀ» ³ôÀϼö ÀÖ½À´Ï´Ù.

±âº»±¸Á¶(Base layout)

  • ´ÙÀ½Àº ±âº»ÀûÀÎ Slab AllocatorÀÇ ±âº»±¸Á¶¸¦ ±×¸²À¸·Î ³ªÅ¸³»¾î º¸¾Ò½À´Ï´Ù. Å©°Ô slab + nft[slab.objects] + object[slab.objects] ±¸Á¶·Î ±¸¼ºµË´Ï´Ù.
    mzslab_base_layout.PNG
    [PNG image (5.99 KB)]


¿¹Á¦¸¦ ÅëÇÑ Slab AllocatorÀÇ Á¢±Ù

  • @¿¹Á¦´Ù¿î·Îµå (2.29 KB) ([http]¿¹Á¦¼Ò½ºÀÇ ÃֽŹöÁ¯ ´Ù¿î·Îµå)
  • ¿¹Á¦¿¡¼­´Â ´ÙÀ½°ú °°Àº ±¸Á¶¸¦ ¼³°è¾È(ÃʱâÈ­°úÁ¤: mzslab_init)À¸·Î ¼³Á¤ÇÏ°í ±¸ÇöÇÏ¿´½À´Ï´Ù. ¼³°è¾È¿¡¼­´Â »ý¼ºÀÚ(Constructor), ¼Ò¸êÀÚ(Destructor)¸¦ °í·ÁÇÏ¿´À¸³ª ¿¹Á¦ÄÚµå ±¸Çö¿¡¼­ ÀÌ ºÎºÐÀº ÀûÀýÇÑ °´Ã¼ÀÇ Ç¥¸éÈ­µÈ ¿¹½Ã±îÁö Á¦½ÃÇÒ ÇÊ¿ä°¡ ¾ø±â ¶§¹®¿¡ »ý·«µÇ¾ú½À´Ï´Ù.
    mzslab_layout.PNG
    [PNG image (26.24 KB)]


  • Slab ÀڷᱸÁ¶
    /*
     Copyright (C) JAEHYUK CHO
     All rights reserved.
     Code by JaeHyuk Cho <mailto:minzkn@minzkn.com>
    */
    
    /* object indexÀÇ ´ÜÀ§¸¦ ³ªÅ¸³»´Â º¯¼öÇüÀÔ´Ï´Ù.
       object¼ö°¡ 65536ÀÌ»óÀÎ °æ¿ì ÀÌ°ÍÀº Á» Å°¿ö¾ß °ÚÁÒ. */
    typedef unsigned short int __mzslab_index_t;
    #define mzslab_index_t __mzslab_index_t
    
    #pragma pack(push,8)
    typedef struct mzslab_ts {
        /* object ÀÇ Å©±â¸¦ ³ªÅ¸³À´Ï´Ù. */
        size_t object_size;
        /* object ¼ö¸¦ ³ªÅ¸³À´Ï´Ù. */
        size_t objects;
        /* ù object ÀÇ Æ÷ÀÎÅÍÀÔ´Ï´Ù.
           ÀÌ ¶ÇÇÑ ·±Å¸ÀÓ¿¡ °è»ê °¡´ÉÇÏÁö¸¸ ¹Ì¸®... */
        unsigned char *entry;
        /* ù¹ø° ÇØÁ¦µÈ Object ÀÇ index¸¦ ÀúÀåÇÕ´Ï´Ù.
           ¸¸¾à ÀÌ °ªÀÌ objectsº¸´Ù °°°Å³ª Å©°Ô µÇ¸é ÇÒ´ç°¡´ÉÇÑ object°¡ ¾ø°Ô µË´Ï´Ù. */
        mzslab_index_t f;
    }__mzslab_t;
    #define mzslab_t __mzslab_t
    #pragma pack(pop)
    


  • mzslab_t ÀÇ ÃʱâÈ­
    mzslab_t * mzslab_init(void *s_page, size_t s_page_size, size_t s_object_size)
    {
        size_t s_index;
    
        mzslab_t *s_slab;
        mzslab_index_t *s_nft; /* next free table */
    
        /* pageÀÇ Ã¹ ¼±µÎºÎºÐÀ» slab±¸Á¶ÀúÀ念¿ªÀ¸·Î »ç¿ëÇÕ´Ï´Ù. */    
        s_slab = (mzslab_t *)s_page;
        
        /* ÇϳªÀÇ object°¡ °¡Áö´Â À¯´ÖÀÇ Å©±â¸¦ ÀúÀåÇصӴϴÙ. */
        s_slab->object_size = s_object_size;
    
        /* ¿©·¯°¡Áö pageÀÇ Å©±â¿¡ µû¸¥ ÀûÀýÇÑ object¼ö¸¦ »êÃâÇϱâ À§Çؼ­ slab index¿µ¿ªÀ» °í·ÁÇÑ »êÃâloop¸¦ »ç¿ëÇÕ´Ï´Ù. */
        s_slab->objects = (s_page_size - sizeof(mzslab_t)) / s_object_size;
        while((s_slab->objects > ((size_t)0)) && ((s_page_size - sizeof(mzslab_t)) < ((s_slab->objects * s_object_size) + (s_slab->objects * sizeof(mzslab_index_t))))) {
            s_slab->objects--;
        }
        if(s_slab->objects <= ((size_t)0)) { /* object¸¦ ´ã±â¿¡ ºÒ°¡´ÉÇÑ Å©±âÀÎ °æ¿ì slabÀº ÃʱâÈ­ ÇÒ¼ö ¾ø½À´Ï´Ù. */
            return((mzslab_t *)0);
        }
    
        /* ù object¸¦ °¡¸£Å°´Â Æ÷ÀÎÅ͸¦ ÀúÀåÇصӴϴÙ. */
        s_slab->entry = ((unsigned char *)(&s_slab[1])) + (s_slab->objects * sizeof(mzslab_index_t));
    
        /* ÇÒ´çµÇÁö ¾ÊÀº objectÀÇ Ã¹¹ø° index¸¦ ÀúÀåÇÕ´Ï´Ù. */
        s_slab->f = (mzslab_index_t)0u;
    
        /* ÇØÁ¦µÈ ¸Þ¸ð¸®·Î Ç¥ÇöÇϱâ À§ÇÏ¿© index¸¦ ÃʱâÈ­ ÇÕ´Ï´Ù. */    
        s_nft = (mzslab_index_t *)(&s_slab[1]);
        for(s_index = ((size_t)0u);s_index < s_slab->objects;s_index++) {
            s_nft[s_index] = s_index + ((size_t)1u);
        }
    
        return(s_slab);
    }
    


  • ÇÒ´ç
    void * mzslab_alloc(mzslab_t *s_slab)
    {
        mzslab_index_t *s_nft = (mzslab_index_t *)(&s_slab[1]);
        void *s_result;
    
        if(s_slab->f >= s_slab->objects) {
            /* ÀÌ °æ¿ì ¸Þ¸ð¸®¿¡ ÇÒ´ç°¡´ÉÇÑ object°¡ ¾ø´Ù°í ÆÇ´ÜÇÏ¸é µÇ°Ú½À´Ï´Ù. */
            s_result = (void *)0;
        }
        else { /* ÇÒ´ç°¡´ÉÇÑ object°¡ ÀÖÀ¸¹Ç·Î À̸¦ ¹ÝȯÇÕ´Ï´Ù. */
            s_result = (void *)(&s_slab->entry[s_slab->f * s_slab->object_size]);
            s_slab->f = s_nft[s_slab->f];
        }
    
        return(s_result);
    }
    


  • ÇØÁ¦
    /* ¿ø·¡ s_slabÀº Àü¿ª cacheÅ×À̺í·Î °¨Ãß°í
       s_ptr¸¸À¸·Î ÃßÃâÇÒ¼ö ÀÖµµ·Ï ±¸ÇöÇÏ´Â°Ô ¹Ù¶÷Á÷ÇÏÁö¸¸
       ÇöÀç ¿¹Á¦¸¦ µé±â À§ÇÑ ºÎºÐÀ̱⿡ ±×³É ÀÎÀÚ·Î ³Ñ°Ü ¹Þµµ·Ï ÇÏ¿© ¼Ò°³ÇÕ´Ï´Ù. */
    void * mzslab_free(mzslab_t *s_slab, void *s_ptr)
    {
        mzslab_index_t *s_nft = (mzslab_index_t *)(&s_slab[1]);
        size_t s_index;
    
        s_index = (size_t)(((unsigned char *)s_ptr) - s_slab->entry) / s_slab->object_size;
    
        s_nft[s_index] = s_slab->f;
        s_slab->f = s_index;
    
        return((void *)0);
    }
    

ID
Password
Join
Expect a letter from a friend who will ask a favor of you.


sponsored by andamiro
sponsored by cdnetworks
sponsored by HP

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-06-22 13:10:38
Processing time 0.0050 sec