Linux內(nèi)核使用了源自于 Solaris 的一種方法，但是這種方法在嵌入式系統(tǒng)中已經(jīng)使用了很長(zhǎng)時(shí)間了，它是將內(nèi)存作為對(duì)象按照大小進(jìn)行分配，被稱為slab高速緩存。

內(nèi)存管理的目標(biāo)是提供一種方法，為實(shí)現(xiàn)各種目的而在各個(gè)用戶之間實(shí)現(xiàn)內(nèi)存共享。內(nèi)存管理方法應(yīng)該實(shí)現(xiàn)以下兩個(gè)功能：

• 最小化管理內(nèi)存所需的時(shí)間
• ***化用于一般應(yīng)用的可用內(nèi)存（最小化管理開銷）

內(nèi)存管理實(shí)際上是一種關(guān)于權(quán)衡的零和游戲。您可以開發(fā)一種使用少量?jī)?nèi)存進(jìn)行管理的算法，但是要花費(fèi)更多時(shí)間來(lái)管理可用內(nèi)存。也可以開發(fā)一個(gè)算法來(lái)有效地管理內(nèi)存，但卻要使用更多的內(nèi)存。最終，特定應(yīng)用程序的需求將促使對(duì)這種權(quán)衡作出選擇。

每個(gè)內(nèi)存管理器都使用了一種基于堆的分配策略。在這種方法中，大塊內(nèi)存（稱為 堆）用來(lái)為用戶定義的目的提供內(nèi)存。當(dāng)用戶需要一塊內(nèi)存時(shí)，就請(qǐng)求給自己分配一定大小的內(nèi)存。堆管理器會(huì)查看可用內(nèi)存的情況（使用特定算法）并返回一塊內(nèi)存。搜索過程中使用的一些算法有 first-fit（在堆中搜索到的***個(gè)滿足請(qǐng)求的內(nèi)存塊）和 best-fit（使用堆中滿足請(qǐng)求的最合適的內(nèi)存塊）。當(dāng)用戶使用完內(nèi)存后，就將內(nèi)存返回給堆。

這種基于堆的分配策略的根本問題是碎片（fragmentation）。當(dāng)內(nèi)存塊被分配后，它們會(huì)以不同的順序在不同的時(shí)間返回。這樣會(huì)在堆中留下一些洞，需要花一些時(shí)間才能有效地管理空閑內(nèi)存。這種算法通常具有較高的內(nèi)存使用效率（分配需要的內(nèi)存），但是卻需要花費(fèi)更多時(shí)間來(lái)對(duì)堆進(jìn)行管理。

另外一種方法稱為 buddy memory allocation，是一種更快的內(nèi)存分配技術(shù)，它將內(nèi)存劃分為 2 的冪次方個(gè)分區(qū)，并使用 best-fit 方法來(lái)分配內(nèi)存請(qǐng)求。當(dāng)用戶釋放內(nèi)存時(shí)，就會(huì)檢查 buddy 塊，查看其相鄰的內(nèi)存塊是否也已經(jīng)被釋放。如果是的話，將合并內(nèi)存塊以最小化內(nèi)存碎片。這個(gè)算法的時(shí)間效率更高，但是由于使用 best-fit 方法的緣故，會(huì)產(chǎn)生內(nèi)存浪費(fèi)。

slab 緩存

Linux 所使用的 slab 分配器的基礎(chǔ)是 Jeff Bonwick 為 SunOS 操作系統(tǒng)***引入的一種算法。Jeff 的分配器是圍繞對(duì)象緩存進(jìn)行的。在內(nèi)核中，會(huì)為有限的對(duì)象集（例如文件描述符和其他常見結(jié)構(gòu)）分配大量?jī)?nèi)存。Jeff 發(fā)現(xiàn)對(duì)內(nèi)核中普通對(duì)象進(jìn)行初始化所需的時(shí)間超過了對(duì)其進(jìn)行分配和釋放所需的時(shí)間。因此他的結(jié)論是不應(yīng)該將內(nèi)存釋放回一個(gè)全局的內(nèi)存池，而是將內(nèi)存保持為針對(duì)特定目而初始化的狀態(tài)。例如，如果內(nèi)存被分配給了一個(gè)互斥鎖，那么只需在為互斥鎖***分配內(nèi)存時(shí)執(zhí)行一次互斥鎖初始化函數(shù)（mutex_init）即可。后續(xù)的內(nèi)存分配不需要執(zhí)行這個(gè)初始化函數(shù)，因?yàn)閺纳洗吾尫藕驼{(diào)用析構(gòu)之后，它已經(jīng)處于所需的狀態(tài)中了。

Linux slab 分配器使用了這種思想和其他一些思想來(lái)構(gòu)建一個(gè)在空間和時(shí)間上都具有高效性的內(nèi)存分配器。

圖 1 給出了 slab 結(jié)構(gòu)的高層組織結(jié)構(gòu)。在***層是 cache_chain，這是一個(gè) slab 緩存的鏈接列表。這對(duì)于 best-fit 算法非常有用，可以用來(lái)查找最適合所需要的分配大小的緩存（遍歷列表）。cache_chain 的每個(gè)元素都是一個(gè) kmem_cache 結(jié)構(gòu)的引用（稱為一個(gè) cache）。它定義了一個(gè)要管理的給定大小的對(duì)象池。

圖 1. slab 分配器的主要結(jié)構(gòu)

每個(gè)緩存都包含了一個(gè) slabs 列表，這是一段連續(xù)的內(nèi)存塊（通常都是頁(yè)面）。存在 3 種 slab：

slabs_full

完全分配的 slab

slabs_partial

部分分配的 slab

slabs_empty

空 slab，或者沒有對(duì)象被分配

注意：slabs_empty 列表中的 slab 是進(jìn)行回收（reaping）的主要備選對(duì)象。正是通過此過程，slab 所使用的內(nèi)存被返回給操作系統(tǒng)供其他用戶使用。

slab 列表中的每個(gè) slab 都是一個(gè)連續(xù)的內(nèi)存塊（一個(gè)或多個(gè)連續(xù)頁(yè)），它們被劃分成一個(gè)個(gè)對(duì)象。這些對(duì)象是從特定緩存中進(jìn)行分配和釋放的基本元素。注意 slab 是 slab 分配器進(jìn)行操作的最小分配單位，因此如果需要對(duì) slab 進(jìn)行擴(kuò)展，這也就是所擴(kuò)展的最小值。通常來(lái)說，每個(gè) slab 被分配為多個(gè)對(duì)象。

由于對(duì)象是從 slab 中進(jìn)行分配和釋放的，因此單個(gè) slab 可以在 slab 列表之間進(jìn)行移動(dòng)。例如，當(dāng)一個(gè) slab 中的所有對(duì)象都被使用完時(shí)，就從 slabs_partial 列表中移動(dòng)到 slabs_full 列表中。當(dāng)一個(gè) slab 完全被分配并且有對(duì)象被釋放后，就從 slabs_full 列表中移動(dòng)到 slabs_partial 列表中。當(dāng)所有對(duì)象都被釋放之后，就從 slabs_partial 列表移動(dòng)到 slabs_empty 列表中。

#p#

一、slab相關(guān)數(shù)據(jù)結(jié)構(gòu)

1）slab高速緩存描述符

struct kmem_cache {   
    struct array_cache   *array[NR_CPUS];//為了提高效率，每個(gè)cpu都有一個(gè)slab空閑對(duì)象緩存   
/* 2) Cache tunables. Protected by cache_chain_mutex */   
    unsigned int batchcount;//從本地高速緩存批量移入或移出對(duì)象的數(shù)目   
    unsigned int limit;//本地高速緩存空閑對(duì)象的***數(shù)目   
    unsigned int shared;   
    unsigned int buffer_size;   
    struct kmem_list3 *nodelists[MAX_NUMNODES];//slab高速緩存空閑，部分空閑，無(wú)空閑slab的三個(gè)鏈表   
   
    unsigned int flags;     /* constant flags */   
    unsigned int num;//每個(gè)slab obj的個(gè)數(shù)   
    unsigned int gfporder;//每個(gè)slab中連續(xù)頁(yè)框的數(shù)目   
    gfp_t gfpflags;//分配頁(yè)框時(shí)，傳遞給伙伴系統(tǒng)的標(biāo)志   
    size_t colour;//slab使用的顏色個(gè)數(shù)   
    unsigned int colour_off; //slab的顏色偏移   
    struct kmem_cache *slabp_cache;  //指向存放slab描述符的chache，內(nèi)部slab此字段為null   
    unsigned int slab_size;//單個(gè)slab的大小   
    unsigned int dflags;        /* dynamic flags */   
    //對(duì)象創(chuàng)建的構(gòu)建函數(shù)   
    void (*ctor) (void *, struct kmem_cache *, unsigned long);   
    //對(duì)象的析構(gòu)函數(shù)   
    void (*dtor) (void *, struct kmem_cache *, unsigned long);   
    const char *name;//slab高速緩存的名稱   
    struct list_head next;//通過該字段，將該cachep鏈接到cachep鏈表上   
}   

2）slab描述符

struct slab {   
    struct list_head list;  //將slab鏈接到各個(gè)slab鏈表上面，slabs_full, slabs_paril, slabs_free   
    unsigned long colouroff;//slab中***個(gè)對(duì)象的偏移   
    void *s_mem; //slab中***個(gè)對(duì)象的地址           
    unsigned int inuse; //有多少對(duì)象正在被使用   
    kmem_bufctl_t free; //表明接下來(lái)使用哪個(gè)空閑對(duì)象   
    unsigned short nodeid;//該slab屬于哪個(gè)內(nèi)存節(jié)點(diǎn)   
} 

slab描述符可能會(huì)被存放在兩個(gè)地方：

外部slab描述符：存放在slab外部，位于cache_size指向的一個(gè)普通高速緩存中。

內(nèi)部slab描述符：存放在slab的內(nèi)部，位于分配給slab的內(nèi)存的***個(gè)頁(yè)框的起始位置。

3）slab隊(duì)列描述符

struct kmem_list3 {   
    struct list_head slabs_partial; //對(duì)象被使用了一部分的slab描述符的鏈表   
    struct list_head slabs_full;//對(duì)象都被占用了的slab描述符的鏈表   
    struct list_head slabs_free;//只包含空閑對(duì)象的slab描述符的鏈表   
    unsigned long free_objects;//高速緩存中空閑對(duì)象的個(gè)數(shù)   
    unsigned int free_limit;   
    unsigned int colour_next;   /* Per-node cache coloring */   
    spinlock_t list_lock;   
    struct array_cache *shared; //指向所有cpu所共享的一個(gè)本地高速緩存   
    struct array_cache **alien; /* on other nodes */   
    unsigned long next_reap;    //由slab的頁(yè)回收算法使用   
    int free_touched;       //由slab的頁(yè)回收算法使用   
} 

4）slab對(duì)象描述符

typedef unsigned int kmem_bufctl_t; 

每個(gè)對(duì)象都有一個(gè)類型為kmem_bufctl_t的對(duì)象描述符，每個(gè)slab描述符都有一個(gè)kmem_bufctl_t類型的數(shù)組來(lái)描述slab中的各個(gè)對(duì)象。其實(shí)該描述符記錄的是下一個(gè)可用的空閑對(duì)象，使用了數(shù)組的索引來(lái)形成一個(gè)對(duì)象鏈表而已。對(duì)象描述符也分為內(nèi)部對(duì)象描述符和外部對(duì)象描述符兩種：

1. 內(nèi)部對(duì)象描述符：存放在slab的內(nèi)部，位于描述符所描述的對(duì)象的前面。
2. 外部對(duì)象描述符：存放在slab的外部，位于高速緩存描述符slabp_cache字段指向的一個(gè)普通高速緩存中，

slab描述符和slab對(duì)象之間的組織圖如下圖所示：

二、slab的本地對(duì)象緩存

Linux2.6為了更好的支持多處理器，減少自旋鎖的競(jìng)爭(zhēng)并更好的利用硬件高速緩存，slab分配器的每個(gè)高速緩存都包含一個(gè)被稱為slab本地高速緩存的每cpu數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)由一個(gè)指向被釋放對(duì)象的指針數(shù)組組成。這樣的話，slab對(duì)象的釋放和分配就只影響到本地的指針數(shù)組，減少了并發(fā)性。只有本地?cái)?shù)組上溢或者下溢時(shí)才會(huì)去涉及slab結(jié)構(gòu)。相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：

struct array_cache {   
    unsigned int avail;//本地高速緩存中可用對(duì)象的個(gè)數(shù)，也是空閑數(shù)組位置的索引   
    unsigned int limit;//本地高速緩存的大小   
    unsigned int batchcount;//本地高速緩存填充或者清空時(shí)使用到的對(duì)象個(gè)數(shù)   
    unsigned int touched;//如果本地高速緩存最近被使用過，置成1   
    spinlock_t lock;   
    void *entry[0];    
} 

同時(shí)在多cpu的環(huán)境下，還存在著一個(gè)共享高速緩存，它的地址被存放在高速緩存描述符的lists.shared字段中，本地共享高速緩存被所有cpu所共享，使得對(duì)象從一個(gè)本地高速緩存移至另一個(gè)高速緩存變的簡(jiǎn)單。

三、slab內(nèi)存著色

比如cache line 32 字節(jié)，字節(jié)0-31一次從內(nèi)存寫入/讀取，字節(jié)32-63一次從內(nèi)存寫入/讀取…..

另外cache對(duì)應(yīng)到內(nèi)存位置不是任意的

Cache 地址0 對(duì)應(yīng)到 內(nèi)存地址0 , 32 ,64 ….

Cache 地址1 對(duì)應(yīng)到 內(nèi)存地址1 , 33 ,65 ….

…

一個(gè)slab大小肯定是整數(shù)頁(yè)，所以起始地址末12位為零， 即都于cache0 對(duì)應(yīng)。然后2個(gè)slab的每一個(gè)obj大小一樣， 所以2個(gè)slab每個(gè)obj都對(duì)應(yīng)相同的cache line.這樣2個(gè)位置相同的obj都要頻繁訪問，比較容易使cache來(lái)回刷新，效率降低。

著色就是在第二個(gè)slab的起始位置空一個(gè)cache line出來(lái)，這樣2個(gè)slab每個(gè)obj對(duì)應(yīng)的cache錯(cuò)開一個(gè)，這樣2個(gè)位置相同的obj即使頻繁訪問，也不會(huì)用一個(gè)相同cache line。

但是這種方法也是有限的，2個(gè)slab里面的obj對(duì)象的訪問比較隨即，不能保證哪兩個(gè)在一個(gè)cache line 里。

#p#

四、slab內(nèi)存的申請(qǐng)

內(nèi)核代碼中通過slab分配對(duì)象的函數(shù)時(shí)kmem_cachep_alloc()，實(shí)質(zhì)上***調(diào)用的函數(shù)是____cache_alloc()，其相應(yīng)源碼解析如下：

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)   
{   
    void *objp;   
    struct array_cache *ac;   
   
    check_irq_off();   
    //通過進(jìn)程所在的cpu的id獲取slab的本地高速緩存   
    ac = cpu_cache_get(cachep);   
    //本地高速緩存中是否有空閑的slab對(duì)象   
    if (likely(ac->avail)) {   
        //有空閑對(duì)象的話，從本地高速緩存數(shù)組上取一個(gè)空閑的對(duì)象來(lái)使用   
        STATS_INC_ALLOCHIT(cachep);   
        //標(biāo)記一下該本地高速緩存最近被使用過   
        ac->touched = 1;   
        //從數(shù)組的***面先取一個(gè)未使用的對(duì)象，HOHO   
        objp = ac->entry[--ac->avail];   
    } else {   
        STATS_INC_ALLOCMISS(cachep);   
        //本地高速緩存中已經(jīng)沒有空閑對(duì)象，需要填充本地高速緩存   
        objp = cache_alloc_refill(cachep, flags);   
    }   
    return objp;   
}   
   
    cache_alloc_refill()用來(lái)填充本地高速緩存，也是slab分配精華的地方，代碼解析如下：   
static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)   
{   
    int batchcount;   
    struct kmem_list3 *l3;   
    struct array_cache *ac;   
   
    check_irq_off();   
    //根據(jù)cpu id得到slab本地高速緩存的數(shù)據(jù)結(jié)構(gòu)   
    ac = cpu_cache_get(cachep);   
retry:   
    //batchcount記錄了此次需要填充多少個(gè)空閑對(duì)象   
    batchcount = ac->batchcount;   
    if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {   
        batchcount = BATCHREFILL_LIMIT;   
    }   
    //獲取到相對(duì)應(yīng)的內(nèi)存節(jié)點(diǎn)上的slab鏈表kmem_list3,每個(gè)內(nèi)存節(jié)點(diǎn)都有自己的一套空閑，部分空閑，非空閑slab鏈表   
    //因?yàn)橄鄳?yīng)cpu訪問自己所屬的內(nèi)存節(jié)點(diǎn)的速度是最快的   
    l3 = cachep->nodelists[numa_node_id()];   
   
    BUG_ON(ac->avail > 0 || !l3);   
    spin_lock(&l3->list_lock);   
   
    //從本地共享高速緩存中往本地高速緩存中填充空閑對(duì)象，要注意對(duì)于numa   
    //系統(tǒng)來(lái)說，往本地高速緩存上填充的空閑對(duì)象也都是該內(nèi)存節(jié)點(diǎn)上的空閑對(duì)象   
    if (l3->shared && transfer_objects(ac, l3->shared, batchcount))   
        goto alloc_done;   
   
    while (batchcount > 0) {   
        struct list_head *entry;   
        struct slab *slabp;   
        //先從部分空閑的slab里面分配空閑對(duì)象，保留完全空閑的slab，因?yàn)榭臻e的   
        //slab在內(nèi)存不足時(shí)是可以回收的   
        entry = l3->slabs_partial.next;   
        //如果沒有了部分空閑的slab，就只能去完全空閑的slab中分配了   
        if (entry == &l3->slabs_partial) {   
            l3->free_touched = 1;   
            entry = l3->slabs_free.next;   
            //如果完全空閑的slab也沒有了，就必須要為slab高速緩存分配新的slab了   
            if (entry == &l3->slabs_free)   
                goto must_grow;   
        }   
   
        slabp = list_entry(entry, struct slab, list);   
        check_slabp(cachep, slabp);   
        check_spinlock_acquired(cachep);   
        //從slab中分配空閑對(duì)象，直到slab中空閑對(duì)象不存在了，或者已經(jīng)分配   
        //了足夠的空閑對(duì)象了   
        while (slabp->inuse < cachep->num && batchcount--) {   
            STATS_INC_ALLOCED(cachep);   
            STATS_INC_ACTIVE(cachep);   
            STATS_SET_HIGH(cachep);   
            //此處獲取空閑對(duì)象   
            ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,   
                                numa_node_id());   
        }   
        check_slabp(cachep, slabp);   
   
        /* move slabp to correct slabp list: */   
        list_del(&slabp->list);   
        //若相應(yīng)slab的空閑內(nèi)存分配完畢，將其掛入slabs_full的slab鏈表中   
        if (slabp->free == BUFCTL_END)   
            list_add(&slabp->list, &l3->slabs_full);   
        else   
            list_add(&slabp->list, &l3->slabs_partial);   
    }   
   
must_grow:   
    l3->free_objects -= ac->avail;   
alloc_done:   
    spin_unlock(&l3->list_lock);   
    //沒有分配到任何的對(duì)象   
    if (unlikely(!ac->avail)) {   
        int x;   
        //為高速緩存申請(qǐng)新的slab   
        x = cache_grow(cachep, flags, numa_node_id());   
   
        /* cache_grow can reenable interrupts, then ac could change. */   
        ac = cpu_cache_get(cachep);   
        if (!x && ac->avail == 0)    /* no objects in sight? abort */   
            return NULL;   
        //重新從頭填充本地高速緩存   
        if (!ac->avail)      /* objects refilled by interrupt? */   
            goto retry;   
    }   
    ac->touched = 1;   
    //返回本地高速緩存***一個(gè)空閑對(duì)象的地址   
    return ac->entry[--ac->avail];   
}   

#p#

五、slab內(nèi)存的釋放

slab內(nèi)存的釋放在函數(shù)kmem_cache_free()中，主要處理部分在__cache_free()函數(shù)中，其代碼解析如下：

static inline void __cache_free(struct kmem_cache *cachep, void *objp)   
{   
    struct array_cache *ac = cpu_cache_get(cachep);   
    check_irq_off();   
    objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));   
    if (cache_free_alien(cachep, objp))   
        return;   
    //本地高速緩存可用的空閑對(duì)象尚未達(dá)到限制，將空閑對(duì)象放入本地高速緩存   
    if (likely(ac->avail < ac->limit)) {   
        STATS_INC_FREEHIT(cachep);   
        ac->entry[ac->avail++] = objp;   
        return;   
    } else {   
        //cache_flusharray()會(huì)將本地高速緩存的一些空閑對(duì)象放入到slab中   
        cache_flusharray(cachep, ac);   
        ac->entry[ac->avail++] = objp;   
    }   
}   
   
static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)   
{   
    int batchcount;   
    struct kmem_list3 *l3;   
    int node = numa_node_id();   
    //一次應(yīng)該將batchcount個(gè)空閑對(duì)象歸還到slab中   
    batchcount = ac->batchcount;   
    check_irq_off();   
    //得到對(duì)應(yīng)內(nèi)存節(jié)點(diǎn)的slab list3,上面記錄著該節(jié)點(diǎn)的slab鏈表   
    l3 = cachep->nodelists[node];   
    spin_lock(&l3->list_lock);   
    //優(yōu)先先歸還到本地共享高速緩存中，注意本地共享高速緩存中的   
    //空閑對(duì)象是僅供該內(nèi)存節(jié)點(diǎn)上的各個(gè)cpu分配使用的，這樣可以使內(nèi)存訪問的效率***。   
    if (l3->shared) {   
        struct array_cache *shared_array = l3->shared;   
        int max = shared_array->limit - shared_array->avail;   
        if (max) {   
            if (batchcount > max)   
                batchcount = max;   
            //將batchcount個(gè)數(shù)組元素copy到本地高速緩存中   
            memcpy(&(shared_array->entry[shared_array->avail]),   
                   ac->entry, sizeof(void *) * batchcount);   
            shared_array->avail += batchcount;   
            goto free_done;   
        }   
    }   
    //在沒有本地高速緩存的情況下，釋放回slab中   
    free_block(cachep, ac->entry, batchcount, node);   
free_done:   
    spin_unlock(&l3->list_lock);   
    ac->avail -= batchcount;   
    //將刪除后剩下的空閑對(duì)象往前移動(dòng)一下，hoho,可能還剩下些空閑對(duì)象   
    memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);   
}   
   
static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects,   
               int node)   
{   
    int i;   
    struct kmem_list3 *l3;   
   
    for (i = 0; i < nr_objects; i++) {   
        void *objp = objpp[i];   
        struct slab *slabp;   
        //先從對(duì)象獲取到其所在的page，再?gòu)膒age得到其所屬的slab   
        //page->lru.prev中記錄了page所屬的slab   
        slabp = virt_to_slab(objp);   
        l3 = cachep->nodelists[node];   
        list_del(&slabp->list);   
        check_spinlock_acquired_node(cachep, node);   
        check_slabp(cachep, slabp);   
        //放入對(duì)應(yīng)的slab   
        slab_put_obj(cachep, slabp, objp, node);   
        STATS_DEC_ACTIVE(cachep);   
        l3->free_objects++;   
        check_slabp(cachep, slabp);   
   
        /* fixup slab chains */   
        //slab所有的對(duì)象都已經(jīng)被歸還   
        if (slabp->inuse == 0) {   
            //slab高速緩存的空閑對(duì)象數(shù)超過了限制，可以釋放掉該slab，以   
            //釋放其所占有的內(nèi)存   
            if (l3->free_objects > l3->free_limit) {   
                l3->free_objects -= cachep->num;   
                slab_destroy(cachep, slabp);   
            } else {   
                //加入到完全空閑slab鏈表中   
                list_add(&slabp->list, &l3->slabs_free);   
            }   
        } else {   
            //加入到部分空閑的slab鏈表中   
            list_add_tail(&slabp->list, &l3->slabs_partial);   
        }   
    }   
}