Սկիզբ » Ուսումնական նյութեր » Օպերացիոն համակարգեր » *Nix-եր » malloc ֊ի անատոմիան։ Մաս 2, malloc ֊ի իրականացումը։

malloc ֊ի անատոմիան։ Մաս 2, malloc ֊ի իրականացումը։

| Մարտ 16, 2015 | Մեկնաբանված չէ |

malloc/kmalloc/vmalloc ֊ընտանիքի ֆունկցիաները (համապատասխանաբար հիշողության ազատման ֆունկցիաներն են՝ free/kfree/vfree) նախատեսված են դինամիկ հիշողության հատկացման համար։ kmalloc ֊ն ու vmalloc֊ը օգտագործվում են միջուկի կոդում։ kmalloc -ը վերադարձնում է ցուցիչ  ֆիզիկական հիշողության մեջ անընդհատ բլոկի վրա, այսինքն հիշողության տվյալ բլոկում բոլոր հասցեները ֆիզիկապես հաջորդում են մեկը մյուսին։ vmalloc֊ը նույնպես վերադարձնում է հիշողության անընդհատ բլոկ, բայց այն տարբերությամբ, որ այդ բլոկը վիրտուալ հիշողությունում է անընդհատ և չի երաշխավորվում այդ բլոկի՝ ֆիզիկական հիշողության մեջ անընդհատությունը։

Hardware device֊ների աշխատանքի համար հաճախ անհրաժեշտ է ֆիզիկապես անընդհատ հիշողության, դրա համար միջուկի կոդում ավելի շատ օգտագործվում է kmalloc֊ը, բացի դա kmalloc ֊ը ավելի արագ է քան vmalloc֊ը։ Բացի այդ kmalloc֊ը կարող է հատկացնել միայն հիշողության փոքր բլոկներ, իսկ vmalloc֊ը՝ համեմատաբար ավելի մեծ հիշողության բլոկներ։

Իսկ ահա malloc֊ը նախատեսված է միայն user space տիրույթում օգտագործման համար։  Այն հատկացնում է որոշակի չափի հիշողություն և վերադարձնում է ցուցիչ դրա սկզբի վրա։ Ընդ֊որում հատկացված հիշողությունը ինիցիալիզացված չէ և հետևաբար ունի անորոշ արժեքներ, ինչպես նաև չի երաշխավորվում այդ հիշողության անընդհատությունը վիրտուլ հասցեական տարածության մեջ։

malloc ―ը հիշողություն է հատկացնում բլոկներով:

header

ՆԿ․ 1․

Ինչպես երևում է վերը բերված նկարից, յուրաքանչյուր հատկացված բլոկ կազմված է header֊ից (գլխագրից) և բուն օգտագործման համար նախատեսված հիշողության տարածությունից։ Header ֊ը պարունակում է ցուցիչ, որը հղվում է հաջորդ բլոկի վրա և պահանջվող բլոկի չափը։ Ընդ֊որում header֊ի չափը հավասարեցվում է ըստ որոշակի data type֊ի, որի նկատմամբ տվյալ մեքենայում ներկայացվում են ամենախիստ պահանջները։

Մեքենաները հիշողությանը դիմում են հիմնականում word (տվյալի տիպ, որը նկարագրում է մեկ մեքենայական բառը, 32 բիթ մեքենաների վրա հավասար է 4 բայթի) չափանի բաժիններով։ Այս իմաստով տվյալների հավասարեցումը կատարվում է այնպես, որ յուրաքանչյուր տվյալ հիշողության մեջ զբաղեցնի այնպիսի հասցե, որը պատիկ է word֊ին։ Տվյալների յուրաքանչյուր տիպ ունի հավասարեցման իր պահանջները, օրինակ char ֊ը կարող է սկսվել ցանկացած հասցեյից, short֊ը կարող է սկսվել հասցեյից, որը պատիկ է 2֊ին, int֊ն ու long֊ը 4-ին, double֊ը 8 ֊ին և այլն։

header ֊ը իրենից ներկայացնում է հետևյալ միավորումը

union header {  
    struct {  
         union header *ptr; // ցուցիչ հաջորդ բլոկի վրա  
         unsigned size;  // բլոկի չափը
    } s;  
    Align x;  
};

Ինչպես տեսնում ենք վերը բերված union header֊ում օգտագործված է s struct֊ն ու x փոփոխականը, որը կոդում ոչ մի տեղ չի օգտագործվում է, բայց գրվում է header֊ում միայն հավասարեցման նպատակով։ Իսկ թե ինչպես է կատարվում այդ հավասարեցումը, հիմա կդիտարկենք։ Այստեղ Align ֊ը  սահմանված է որպես,

typedef struct max_align_t Align;

max_align_t֊ն իրենից ներկայացնում է տվյալների որոշակի տիպ, որի նկատմամբ տվյալ մեքենայում սահմանված են ամենախիստ պահանջները ու եթե այն այդ պահանջներին բավարարում է, նշանակում է մյուս տիպերն էլ կբավարարեն։ Օրինակ՝ եթե ինչ֊որ մեքենայում long double ֊ը պահանջում է 8 բայթանի հավասարեցում (տվյալ long double փոփոխականը կարող է ունենալ միայն 8-ին պատիկ հասցե) և ոչ մի այլ տվյալի տիպ չի պահանջում այդ չափ մեծ հավասարեցում, դա նշանակում է, որ տվյալ մեքենայում long double֊ը այն տիպն է, որի նկատմամբ ներկայացվում են ամենախիստ պահանջները։ max_align_t ֊ն տիպը սահմանաված է stddef.h գլխագրային ֆայլում, որը գտնվում է այստեղ

/usr/lib/gcc/i686-linux-gnu/4.8/include/stddef.h

Բայց քանի֊որ որոշել ենք, որ մեր կոդերը մինիմալ կախվածություն պետք է ունենան libc֊ից, եկեք վերը տրված path֊ում նկարագրվածի պես մենք էլ սահմանենք max_align_t փոփոխականը

struct max_align_t {
    long long __max_align_ll __attribute__((__aligned__(__alignof__(long long))));
    long double __max_align_ld __attribute__((__aligned__(__alignof__(long double))));
} ;

Այստեղ __attribute__֊ները օգտագործված են, որպեսզի ստիպեն կոմպիլյատորին կատարել հավասարեցում, երբ max_align_t struct―ը հանդիսանում է այլ struct֊ի անդամ փոփոխական։

Հաշվելով մեր max_align_t ֊ի չափը մենք կիմանանք այն մեծությունը, որով պետք է հավասարեցվի մեր union header֊ը։ Բայց նաղքան այդ բերենք struct֊ի չափը հաշվելու ընդհանուր մոտեցումը, որտեղ կարելի է առանձնացնել հետևյալ երկու կարևոր մոտեցումները․

  1. struct֊ի մեջ յուրաքանչյուր տվյալ կամ անդամ փոփոխական սկսվում է հավասարեցված հասցեյից,
  2. ընդհանուր struct֊ի չափը հավասարեցվում է այնպես, որ այն պատիկ լինի իր պարունակած ամենամեծ չափի տվյալների տիպին։

Օրինակ՝ ունենք հետևյալ struct֊ը

struct s
{
   int b;
   double c;
   char a;
}

Հիմա s struct ֊ի չափը կլինի

sizeof(s) = b[4 բայթ] + լրացում[4 բայթ] + c[8 բայթ] + c[1 բայթ] + լրացում[7 բայթ]

b -ն զբաղեցնում է 4 բայթ, բայց քանի որ double֊ը պահանջում է հասցե, որը պատիկ կլինի 8 թվին, դրա համար b֊ի 4 բայթին գումարվում է մինչև 8 բայթ լրացման 4 բայթը, արդյունքին գումարվում է double֊ի 8 բայթը։ Քանի֊որ char֊ը կարող է ունենալ կամայական հասցե, ապա եղած արդյունքին պարզապես գումարվում է char֊ի 1 բայթ և արդյունքում ստացվում է 17 բայթ։ Բայց քանի որ մեր struct s֊ի ամենամեծ չափ ունեցող անդամը double ֊ն է, որը 8 բայթ է զբաղեցնում, ապա ելնելով վերը բերված րդ մոտեցումից struct s֊ի չափը պետք է պատիկ լինի double c ֊ին, այսինքն ին։ Դրա համար մեր ունեցած 17 բայթերին գումարվում է մինչև 24 լրացման լրացուցիչ 7 բայթերը։

Հիմա, երբ պարզ է struct֊ի չափը հաշվելու մոտեցումը, հաշվենք մեր max_align_t ֊ի չափը, քանի ֊որ

long long __max_align_ll փոփոխականը 8 բայթ է,

long double __max_align_ld փոփոխականը 12 բայթ,

struct -ի չափը կլինի՝

sizeof(struct max_align_t) = __max_align_ll[8 byte] + __max_align_ld[12 byte] + լրացում[4 byte] = 24 բայթ

Սա այն դեպքում, երբ long double֊ի հավասարեցման չափը 8 բայթն է, այն կարող է լինել նաև 16, բայց այդ դեպքը մենք չենք դիտարկի։

Այժմ պարզ է, որ մեր struct max_align_t ֊ի կամ որ նույնն է մեր փոփոխականի  չափը 24 ֊է։ Քանի որ C-ում union֊ի մեջ բոլոր անդամները ունեն նույն շեղումը, ապա որպես union֊ի չափ վերցվում է դրա ամենամեծ չափ ունեցող փոփոխականի չափը, քանի֊որ մեր դեպքում struct s-ի չափը հավասր է 8 ֊ի (ptr[4 բայթ] + size[4 բայթ] = 8), ապա մեր union header ֊ի չափը կլինի 24։ Սա այն չափն է, որին պետք է պատիկ լինի malloc֊ի կանչի արդյունքում օգտագործողին վերադարձվող հիշողությունը: Ընդ որում malloc֊ը վերադարձնում է ցուցիչ ոչ թե բլոկի սկզբի, այսինքն header ֊ի, այլ հատկացված ազատ տարածության վրա։

malloc ֊ը օպերացիոն համակարգից վերցնում է հիշողություն ըստ անհրաժեշտության։ Հիշողությունը պահվում է վերը նկարագրված բլոկների միջոցով, ընդ֊որում յուրաքանչյուր բլոկ ունի ցուցիչ հաջորդ բլոկի վրա։ Իսկ ամենավերջի բլոկը ունի ցուցիչ առաջին բլոկի վրա։ Այսպիսով malloc֊ը հիշողությունը պահում է ցիկլիկ կապակցված ցուցակի տեսքով, որը կոչվում է free-list:  Եթե ծրագրավորողի կողմից պահանջվել է հիշողություն, ապա սկզբում դիտարկվում է free-list֊ը, այնքան, քանի դեռ չի գտնվել բավականաչափ մեծ։ Այս ալգորիթմը կոչվում է առաջին համապատասխան բլոկի փնտրման ալգորիթմ։ Համապատասխան  բլոկի փնտրման մյուս ալգորիթմը փնտրում է այն բլոկը, որը եղածներից ամենափոքրն է և մեծ կամ հավասար է պահանջվող չափին։ Եթե գտնվում է այնպիսի բլոկ, որը չափը ճիշտ հավասար է տրված չափին, ապա այդ բլոկը կցվում է free-list ֊ին և վերադարձվում դրա header֊ին հաջորդող տարածության վրա ցուցիչ։ Եթե free-list պահանջներին բավարարող ոչ մի բլոկ չի գտնվում, ապա կատարվում է օպերացիոն համակարգից որոշակի հիշողությամբ բլոկի հարցում և ստացված բլոկը կցվում է free-list֊ին։

Գրենք malloc֊ի կոդը․

void *_malloc(unsigned nbytes)  
{  
    Header *p, *prevp;  
    unsigned nunits;  
  
    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;  
  
    if ((prevp = freep) == NULL) {  
        /*
         * The base variable is the global, static variable therefor all its data-member are initialized to 0 by default.
         * The freep variable means the head or start of the free-list and because free-list is cyrcular, each time updated.
         * */
        base.s.ptr = freep = prevp = &base;  // starting initilializations
        base.s.size = 0;  
    }  
    /*
     * keeps the previous pointer prevp and iterates through free-list if there is no big-enough block and continues prior to accomplish the end of the free-list.
     * if there is big-enough block and when its size equals to requested size, the next pointer of the prevp starts to point to the next block after p pointer. Thereby it removes this block and return
     * pointer after the head of this block.
     * */
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {  
  
        if (p->s.size >= nunits) {  
            if (p->s.size == nunits) {  
                prevp->s.ptr = p->s.ptr;  
            } else { 
                /*
                 * cuts the tail of the block
                 * */
                p->s.size -= nunits; // allocate the tail of the list. Calculate the difference between p->s.size and nunits then increase the p pointer by this diffference.
                p += p->s.size;  
                p->s.size = nunits;  
            }  
            freep = prevp; // update the start(head) of the free-list, now the prevp starts to point to freep and freep now is the start of the free-list. 
            return (void *)(p+1); // The bolck containes the header and free space. And p+1 means that p starts to point to free space (after header) 
        } 
        /*
         * if it is the end of the free-list and there is not a memory, it requests to os to allocate the block of the memory.
         * p == freep means that is reached to the end of the free-list.
         * */
  
        if (p == freep)  
            if ((p = morecore(nunits)) == NULL)  
                return NULL;  
    }  
}

Այստեղ օգտագործված է static Header տիպի  base  փոփոխականը, որը պետք է միայն սկզբում free-list ֊ն սկզբնարժեքավորելու համար։ Քանի որ այն գլոբալ, ստատիկ փոփոխական է, ապա նրա բոլոր անդամները լռությամբ սկզբնարժեքավորվում է 0֊ով։

Քանի որ free-list ֊ը կապակցված ցուցակ է, այն չունի ոչ վերջ, ոչ էլ սկիզբ։ Կոդում օգտագործված է freep փոփոխականը, որը ցույց է տալիս free-list  -ին նախորդ էլեմենտի վրա, երբ ցուցակում գտնվել է բավարար չափի ազատ հիշողություն պարունակող բլոկ, իսկ երբ չի գտվնել այդպիսի բլոկ և ցուցակի վերջն է, ապա freep֊ն սկսում է ցույց տալ ցուցակի տվյալ էլէմենտի վրա, որն էլ ցուցակի պայմանական սկիզբն է։

nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

Այս տողով կլորացնում ենք պահանջվող հիշողության չափը։ Հիմա կարող էք ասել, թե ինչու չենք ուղղակի պահանջվող nbytes բաժանում header֊ի չափի վրա (քանի որ բլոկի չափը պատիկ է header֊ի չափին)։ Եկեք փորձենք, ենթադրենք header չափը 5 ֊է և պահանջվում է 8 բայթ հիշողություն, այդ դեպքում 8/5 արդյունքը կկլորացվի ամբողջ թվի ստորին սահմանով ՝ 8/5 = 1, բայց իրականում այստեղ պահանջվում է 2 բլոկ։ Հիմա նթադրենք պահանջվում է 10 բայթ, եթե օգտագործենք (10/5) + 1, ապա կստանանք 3 բլոկ, բայց իրականում պահանջվում է 2 բլոկ։ Այդ պատճառով կլորացման ճիշտ բանաձևը վերը բերվածն է․ վերևում մենք ուղղակի պահանջվող nbytes  ֊ին ավելացնում ենք Header ֊ի չափը, քանի որ Header նույնպես բլոկի մաս է կազմում։

for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)

Այս տողով պտտվում ենք free-list վրայով, քանի դեռ return չենք եղել եկող երկու return -րից որևէ մեկով։

if (p->s.size >= nunits) {  
            if (p->s.size == nunits) {  
                prevp->s.ptr = p->s.ptr;  
}

ստուգում ենք, արդյո՞ք ընթացիկ բլոկի չափը մեծ է պահանջվող  nunits ֊ից, եթե այո, ապա ստուգում են հավասարի դեպքը, եթե հավասար է, ապա տեղի է ունենում այն ինչը ցույց է տրված նկարում․

blockՆկ․ 2.
Այսինքն ընթացիկ p բլոկը հանվում է free-list֊ից և prevp֊ի ցուցիչը սկսում է ցույց տալ p֊ի հաջորդ էլեմենտի վրա։

else { 
                /*
                 * cuts the tail of the block
                 * */
                p->s.size -= nunits; // allocate the tail of the list. Calculate the difference between p->s.size and nunits then increase the p pointer by this diffference.
                p += p->s.size;  
                p->s.size = nunits;  
            }

Այստեղ պահանջվող հիշողությունը հատկացնում ենք բլոկի վերջից, եթե բլոկի չափը մեծ է պահանջվող nunits ֊ից, ապա p->s.size -= nunits տողով ստանում ենք այն չափը, որը պետք է գումարենք -ին, որպեսզի այն սկսի ցույց տալ պահանջվող nunits չափի բլոկի վրա՝ դրա վերջից, ինչն էլ պատկերված է նկարում։

block2

Նկ․ 3.

Հետևյալ 2 տողերից առաջինով freep ցուցիչը դնում ենք prevp ֊ի վրա, իսկ մյուս տողով վերադարձնում ենք բլոկը, բայց թողնելով header-ը (քանի որ բլոկը պատիկ է header֊ի չափին, ապա p+1 անելով կընկնենք header֊ի վերջի կամ ազատ տարածությամբ բլոկի վրա, տես նկար 4․)։

freep = prevp; //update the start of the free-list, now the prevp starts to point to freep and freep now is the start of the free-list. 
return (void *)(p+1); //The bolck containes the header and free space. And p+1 means that p starts to point to free space (after header)

block_3Նկ․ 4․
Եթե հասել ենք ցուցակի վերջին և ազատ հիշողությամբ բլոկ չենք գտնում, ապա հարցում ենք կատարում օպերացիոն համակարգին՝ պահանջվող բլոկը ստանալու համար․

if (p == freep) {  
            if ((p = morecore(nunits)) == NULL)  
                return NULL; 
}

morecore ֆունկցիան դիմում է օպերացիոն համակարգին՝ հիշողություն ստանալու համար։

static Header *morecore(unsigned nu)  
{  
    char *cp;  
    Header *up;  
  
    if (nu < NALLOC) // (1)  
        nu = NALLOC;  
  
    cp = (char*)__sbrk__(nu * sizeof(Header));  // (2)
    if (cp == (char *) -1)  
        return NULL;  
  
    up = (Header *) cp;  
    up->s.size = nu;  
    _free((void *)(up + 1));  // (3) The bolck containes the header and free space. And up + 1 means performing _free only for free space (free space comes after header, the header does not change) 
  
    return freep;  
}

Այստեղ, կարծում եմ ամեն ինչ պարզ է, միայն պետք նշել հետևյալ տողերը.

  • (1) տողում ստուգում ենք, եթե պահանջվող չափը փոքր է 1024 ֊ից, ապա պահանջվող չափին վերագրում ենք 1024․ միանգամից վերցվում է ավելի շատ հիշողություն, որպեսզի ամեն անգամ անհրաժեշտութուն չլինի համակարգային կանչ կատարել և դանդաղացնել կոդերը։
  • (2) տողում գրված է այն, ինչը դիտարկել ենք առաջին մասում, այստեղ __sbrk__ ֊ին որպես պարամետր ենք տալիս հիշողության չափը, այդ նպատակով բլոկների թիվը բազմապատկում ենք header֊ի չափով՝  nu * sizeof(Header) (բլոկի չափը պատիկ է Header֊ի չափին)։
  • (3) ավելացնում ենք օպերացիոն համակարգից ստացված բլոկը free-list ֊ի մեջ և վերադարձնում ենք up + 1, որը նույն իմաստը ունի ինչը պատկերված է Նկ․4․ ֊ում, ուղղակի վերադարձնում ենք ցուցիչ, բայց թողնելով header֊ը (վերադարձնում ենք ցուցիչ header ֊ից հետո եկող բլոկի վրա) 

malloc֊ի վերաբերյալ այսքանը։ Նյութը գրելու ընթացքում աշխատել եմ մաքսիմալ բացատրել այն, ինչը գրված է կոդերում և առհասարակ մանրամասնել malloc ֊ի կառուցվածքը ։ Այդ պատճառով նյութը կարող է հագեցած թվալ, երբեմն էլ գուցե որոշ մտքեր կարող են կրկնվել։ Խնդրում եմ ներողամիտ լինել , ուղղակի ուզեցել եմ, որ կարդալուց հետո ամեն ինչ հասկանալի լինի նրանց համար, ովքեր նոր են ծանոթանում նյութին։

Անկեղծորեն ասած չէի սպասում, որ հոդվածը այսքան կերկարի, դրա համար free ֆունկցիայի վերաբերյալ կգրվի առանձին նյութ՝ մաս 3֊ը։

Ամբողջական մոդերը՝ այստեղից։

malloc ֊ի անատոմիան։ Մաս 2, malloc ֊ի իրականացումը։, 10.0 out of 10 based on 8 ratings

Նշագրեր: ,

Բաժին: *Nix-եր, C և C++, Ժեշտ, Ծրագրավորում

Կիսվել , տարածել , պահպանել

VN:F [1.9.20_1166]
Rating: 10.0/10 (8 votes cast)

Մեկնաբանեք

Կհաստատվեն միայն մեսրոպատառ հայերենով գրած մեկնաբանությունները

287