Thursday, January 24, 2013

সরল মেমোরি ম্যানেজার

μnix এর জন্য খুব সাধারণ একটা মেমোরি ম্যানেজার বানিয়েছিলাম কিছুদিন আগে। বর্তমানে এটার স্লথগতির জন্য এটাকে আর ব্যবহার করছি না। তবে মেমোরি ম্যানেজার কিভাবে বানানো যায় সেটার একটা উদাহরণ হতে পারে। এটা একটা লিংকড লিস্ট ব্যবহার করে বানানো। অপারেটিং সিস্টেমের জন্য এর চেয়ে ভাল ডাটা স্ট্রাকচার ব্যবহার করতে হবে। বর্তমানে আমি Splay Tree ব্যবহার করছি। অনেকে বলেন AVL Tree ব্যবহার করার কথা। ডেমো এর সুবিধার জন্য এটাকে একটা ইউজার মোড অ্যাপ্লিকেশন হিসাবে দিলাম (টেস্ট করার জন্য অপারেটিং সিস্টেম বানাতে হলে বিপদ!)।

#include "stdio.h"
#include "memory"

#define SIZE 1024*1024
#define MEMORY_USED 0x1
#define DEAD_SIGN 0xEFBEADDE

#define SIGN 0xABCD08EF

#define panic(message)

#define assert(cond) if(!cond){panic("ASSERTION FAILED")}

#define INCLIDE_SANITY_CHECK_CODE

struct memblk{
#ifdef INCLIDE_SANITY_CHECK_CODE
    int signature;
#endif

    memblk *prev,*next;
    unsigned int managed_data, size;
    void *memory;
};

#define MEM_BLK_STRUCT_SIZE (sizeof(memblk) - sizeof(void*))

void *block = NULL;
memblk *head = NULL;

memblk* find_free_block(unsigned int size)
{
    assert(size);

    memblk *cur_blk = head, *free_blk = NULL;

    while(!free_blk)
    {
        if(!(cur_blk->managed_data & MEMORY_USED) && cur_blk->size >=size)
        {
            free_blk = cur_blk;
            break;
        }

        if(cur_blk->next == NULL)
        {
            break;
        }

        cur_blk=cur_blk->next;
    }

    return free_blk;
}

void split_block(memblk *free_blk, unsigned int size)
{
 assert(free_blk->size > (size + MEM_BLK_STRUCT_SIZE));

    //create a new block as next block
    void *address = &(free_blk->memory);
    memblk *next = (memblk *)((int)address + size);
    memset(next, 0, MEM_BLK_STRUCT_SIZE);
#ifdef INCLIDE_SANITY_CHECK_CODE
    next->signature = SIGN;
#endif
    next->prev = free_blk;
    next->next = free_blk->next;
    next->size = free_blk->size - (size + MEM_BLK_STRUCT_SIZE);

    free_blk->next = next;
    free_blk->size = size;
}


void * mem_alloc(unsigned int size)
{
    assert(size);

    if(size<1)
    {
        return NULL;
    }

    memblk* free_blk = find_free_block(size);

    if(free_blk == NULL)
    {    
        return NULL;
    }    
    
    if(free_blk->size > (size + MEM_BLK_STRUCT_SIZE))
    {
        split_block(free_blk, size);
    }
    
    free_blk->managed_data |= MEMORY_USED;
    return &(free_blk->memory);
}

void merge_blocks(memblk *left_blk, memblk *right_blk)
{
    assert(left_blk);
    assert(right_blk);
    assert(!(left_blk->managed_data & MEMORY_USED));
    assert(!(right_blk->managed_data & MEMORY_USED));

    left_blk->next = right_blk->next;
    left_blk->size += (right_blk->size + MEM_BLK_STRUCT_SIZE);

    if(right_blk->next)
    {
        right_blk->next->prev = left_blk;
    }

#ifdef INCLIDE_SANITY_CHECK_CODE
    memset(right_blk, 0xC3, MEM_BLK_STRUCT_SIZE);
#endif
}

void mem_free(void *address)
{
    assert(address);

    memblk *block = (memblk *)((int)address - MEM_BLK_STRUCT_SIZE);

#ifdef INCLIDE_SANITY_CHECK_CODE
    memset(address, 0xAC, block->size);
#endif

    block->managed_data &= ~MEMORY_USED;

    memblk *left_blk = block->prev;
    memblk *right_blk = block->next;
    memblk *cur_blk=block;
    if(left_blk && !(left_blk->managed_data & MEMORY_USED))
    {        
        merge_blocks(left_blk, cur_blk);
        cur_blk = left_blk;
    }

    if(right_blk && !(right_blk->managed_data & MEMORY_USED))
    {
        merge_blocks(cur_blk, right_blk);
    }
}

void print_heap()
{
    memblk *cur_blk=head;
    int count = 0;

    while(cur_blk)
    {
        printf("Block %d: Address: %d Next %d Prev %d Size: %d Used=%s\n", count, cur_blk, cur_blk->next, cur_blk->prev, cur_blk->size, (cur_blk->managed_data & MEMORY_USED)?"Yes":"No");
        count++;
        cur_blk=cur_blk->next;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    block = malloc(SIZE);
    memset(block, 0, SIZE);

    head = (memblk*)block;
#ifdef INCLIDE_SANITY_CHECK_CODE
    head->signature = SIGN;
#endif
    head->prev = NULL;
    head->next = NULL;
    head->managed_data = 0;
    head->size = SIZE - MEM_BLK_STRUCT_SIZE;

    print_heap();
    printf("-------------------------------------------\n");
    void *mem=mem_alloc(16);
    memset(mem, 0xD1, 16);

    print_heap();
    printf("-------------------------------------------\n");

    void *mem2=mem_alloc(32);
    memset(mem2, 0xD2, 32);

    print_heap();
    printf("-------------------------------------------\n");


    void *mem3=mem_alloc(64);
    memset(mem3, 0xD3, 64);

    print_heap();
    printf("-------------------------------------------\n");

    mem_free(mem2);

    print_heap();
    printf("-------------------------------------------\n");


    mem_free(mem);

    print_heap();
    printf("-------------------------------------------\n");

    mem_free(mem3);

    print_heap();
    printf("-------------------------------------------\n");

    return 0;
}

Monday, January 7, 2013

মুহম্মদ জাফর ইকবাল এবং আমার কিছু স্মৃতি

স্কুল/কলেজে পড়ার সময় আমি যে টাকা পেতাম (সেটা খুব বেশি না) তার ৯০% যেত গল্পের বই কিনতে। আমার সংগ্রহে সেবার বই ছাড়া মুহম্মদ জাফর ইকবালের সাইন্স ফিকশন বইই ছিল সবচে' বেশি । আমার এক বন্ধুর ভাই যাকে আমরা টারজান ভাই ডাকি জোমাক নামে একটা কোম্পানিতে কাজ করতেন। এই কোম্পানিটা যমুনার উপর তখন ব্রিজ বানাচ্ছিল যে হুন্দাই কোম্পানির কাজ তদারকি করত। টারজান ভাইয়ের অনেক আগে থেকে কম্পিউটার এবং ইন্টারনেট ছিল। আমি মুহম্মদ জাফর ইকবালকে একটা ইমেইল করতে চাইলাম। উনি বললেন ইংরেজিতে লিখে দিতে। আমি যা লিখেছিলাম তার বাংলা করলে এরকম হয়- "ডিয়ার মুহম্মদ জাফর ইকবাল, আমি আপনার লেখা বেশিরভাগ বই পড়েছি। ...... ...আমি আপনার সাথে একবার দেখা করতে চাই। ইতি - কুয়াশা"। নিজের নাম লিখতে লজ্জা লাগছিল তাই কুয়াশা লিখেছিলাম। উত্তরে তিনি লিখেছিলেন "... বাংলাদেশ একটা খুবই ছোট দেশ। একদিন নিশ্চয়ই তুমি আমার সাথে দেখা করতে পারবে...." ।

এরপর শাহজালাল বিশ্ববিদ্যালয়ে ভর্তি পরীক্ষা দিতে গিয়ে প্রথম দেখলাম ওনাকে মদনমোহন কলেজে। সবার আগে ভর্তি পরীক্ষা - ১৯ ফেব্রুয়ারী ১৯৯৯। কোন ধারণা নাই কেমন পরীক্ষা হলে ভর্তি হওয়া যাবে। যাকেই জিজ্ঞাসা করি কতগুলা হইছে বলে ৭০-৭৫ টা। বাড়ি ফিরে গুনে দেখলাম আমার ৬৪টা হয়েছে ঠিক ৮০ টা প্রশ্নের মধ্যে। আশা ছেড়ে দিলাম সাস্টে ভর্তি হওয়ার। ২৮ তারিখে রেজাল্ট হল। আমি যেটার আর খোঁজ রাখি নাই। পরে ২ তারিখে রাজশাহীতে আমার এক বন্ধু বলল যে সাস্টের পরীক্ষার রেজাল্ট হয়েছে। আমি আমাদের কলেজের পিছনের পাবলিক লাইব্রেরিতে গিয়ে রেজাল্ট দেখলাম। সিরিয়াল অনুযায়ী সি.এস.ই তে ভর্তি হতে পারব দেখে প্রথমে বিশ্বাস হচ্ছিল না। ভাবলাম নিশ্চয়ই রোল নম্বর ভুল করছি- যেটা আছে সিরাজগঞ্জে আমার বাসায়। লাইব্রেরিয়ান খুব ভাল মানুষ- উনি আমাকে কপি করার জন্য পত্রিকাটা ফটোকপির দোকানে নিয়ে যেতে দিলেন। আমি ২ দিন পর বাড়িতে এসে মিলিয়ে দেখলাম যে ঠিকই আছে রোল নম্বর। এরপর বাকি বিশ্ববিদ্যালয়ের পরীক্ষার প্রস্তুতি মাথায় উঠল।

স্কুল থেকেই আমার কম্পিউটারের প্রতি বাড়াবাড়ি রকম আগ্রহ ছিল। কিন্তু তারপরও আমি ইন্টার পাশ করার আগে কম্পিউটার ছুয়ে দেখতে পারি নাই। "সি এন্ড ই জার্নাল" নামে একটা পত্রিকা বের হত যেটার আমি নিয়মিত গ্রাহক ছিলাম। সেটাতে একবার লিখলাম Z80 কম্পিউটার কোথায় পাওয়া যাবে। আমি চিন্তা করে দেখেছিলাম যে কম্পিউটার কেনার জন্য আমি ২-৫ হাজার টাকা সর্বোচ্চ ব্যয় করতে পারব। যাই হোক উত্তর পেলাম অত পুরাতন কম্পিউটার আর পাওয়া যাবে না। ১০-১৫ হাজার টাকায় পুরাতন একটা স্ট্যান্ডার্ড কম্পিউটার পাওয়া যাবে। ভাবলাম যে বানানো যায় কিনা। স্কুল থেকেই ইলেকট্রনিক্স আমার হবি ছিল। কিন্তু খোঁজ নিয়ে দেখলাম পার্টস পাওয়া সম্ভব না। কম্পিউটর সেন্টারের কোর্স ফিও নাগালের বাইরে। তারপরও সেটা শুধু টাইপ শেখা জাতীয় কোর্স হওয়ায় আর আমাকে তার বাইরে কিছু করতে দিবে না বলে আর যাইনি ওদের কাছে। ("সি এন্ড ই জার্নাল" এর যে কপিতে আমার চিঠিটা ছাপা হয়েছিল সেটার কপি যদি থাকে তাহলে আমার চিঠির একটা স্ক্যান কপি দিলৈ কৃতজ্ঞ থাকব)। একবার চুরি করে আমার এক কাজিনের বন্ধুর কম্পিউটার ব্যবহার করতে যেয়ে ধরা পড়ে কেলেঙ্কারি অবস্থা। চারতলা থেকে নীচে ফেলে দিবেন বলেছিলেন।

৫মে ভর্তি হতে গেলাম সাস্টে। ভর্তি ইন্টারভিউএ কোন বিষয়ে ভর্তি হব জিজ্ঞাসা করলেন ভর্তি কমিটির চেয়ারম্যান। আমি বললাম কম্পিউটার সায়েন্স। মুহম্মদ জাফর ইকবাল আমার দিকে ভর্তি ফরমটা এগিয়ে দিলেন এবং সেটাতে সাক্ষর করার পর উনি হটাৎ করে "জাফর স্যার" হয়ে গেলেন। এই সাক্ষরের পর আরেকটা বিশাল ফরম পুরণ করতে হয় বাইরে গিয়ে - যেটাতে স্বাক্ষর নেন সেটা কি ফরম আর মনে নাই। আমি কম্পিউটার সায়েন্সে ভর্তি হতে চাই এটা নিয়ে ভর্তি কমিটির অন্যান্য স্যারেরা হয়ত খুবই হতাশ হয়েছিলেন। কিন্তু আমি কম্পিউটার সায়েন্স শুধু জনপ্রিয় সাবজেক্ট বলে পড়তে চাই নি। কম্পিউটার সায়েন্সের প্রতি আমার আগ্রহ সম্ভবত টিনেজ ছেলেদের মেয়েদের প্রতি যে আগ্রহ থাকে তার সাথে তুলনা করা চলে। (মজার ব্যাপর হচ্ছে ঠিক ৮ বছর পর ৫ মে আমি মাইক্রোসফটে ইন্টারভিউ দিতে যাই হংকং) ।

১১ জুলাই ওরিয়েন্টেশন হল। সেখানে বিভিন্ন জন বিভিন্ন কথা বলল। কে যেন বিল গেটস হতে চাইল। আমি বললাম আমার যা খুশি সেটা আমি পড়তে পারব কিনা। জাফর স্যার উত্তর দিয়েছিলেন এটা একটু মুশকিল হবে। যাই হোক আমি সত্যি সত্যি আমার যা ইচ্ছা তাই পড়েছি। যে সাবজেক্ট ভাল লেগেছে সেটাতে A+ পেয়েছি। যেটা ভাল লাগেনি সেটাতে পাশ করতে হিমশিম খেয়েছি। ৮ সেমিস্টারের কোর্স ১১ সেমিস্টারে শেষ করেছি। তাও হতনা যদি জাফর স্যার ঝাড়ি দিয়ে পরীক্ষা না দেয়াতেন। আমি খুব একটা খারাপ ছাত্র ছিলাম না- শুধু হাই স্কুলে একবার অংকে ২৫ পেয়েছিলাম ১০০ তে- বাসায় বলেছিলাম ৫০ এর মধ্যে পরীক্ষা হয়েছে। কিন্তু বিশ্ববিদ্যালয়ে যাচ্ছেতাই অবস্থা।

জাফর স্যার কম্পিউটার ল্যাবটা ২৪ ঘন্টা উম্মুক্ত করে দিয়েছিলেন। আমি অনেক রাত ল্যাবে কাটিয়েছি (বাসায় পিসি ছিল না ফার্স্ট ইয়ারে)। দিনে ১০ ঘন্টার বেশি টার্বো-প‌্যাসকেল আই.ডি.ই খুলে এটা সেটা করার চেষ্টা করতাম। টার্বো-প‌্যাসকেল সফটওয়ারটা যখন খুশি ব্যবহার করতে পারার স্বাধীনতাটা আমার কাছে এত আনন্দের ছিল যেটা ভেবে এখনও আমি অবাক হই।

জাফর স্যার পৃথিবীর বড় বড় বিশ্ববিদ্যালয়ে পড়েছেন, পড়িয়েছেন। বিশ্বের সেরা ল্যাবে গবেষনা করেছেন। ওনার অবাক হওয়ার মত কিছু করা খুবই কঠিন, যদিও ওনার পরীক্ষায় নম্বর পাওয়া আবার খুবই সহজ। ফোর্থ ইয়ারে ফাইবার অপটিক কম্যুরিকেশন কোর্সটা নিয়েছিলেন জাফর স্যার। সেটার ল্যাবে একটা এক্সপেরিমেন্ট ছিল। যেটাতে গিগাহার্টস ফ্রিকোয়েন্সির একটা সিগন্যাল ফাইবারের মধ্যে দিয়ে পাঠাতে হয়। এটার একটা মুশকিল হচ্ছে অসিলোস্কোপের তারটা যথেষ্ঠ ভাল মানের না হওয়ায় নয়েজ আসত আউটপুটে। আমরা দুইদিন বিভিন্নভাবে চেষ্টা করে একবারে নিঁখুত আউটপুট দেখাতে পেরেছিলাম। স্যার একটু অবাক হয়েছিলেন। খুবই ছোট ঘটনা। হয়ত আমার টিমমেট শামস বা নাসিরেরও মনে নেই। কিন্তু ছাত্র হিসাবে এরকম ছোট ছোট সাফল্যই আমি পেয়েছি। আর এই ল্যাবে A+ পেয়েছি ফাইনাল ভাইবাতে প্রত্যেকটা প্রশ্নের উল্টা উত্তর দেয়ার পরও।

শেষ কোর্সটার রেজাল্ট যখন পেলাম তার কিছুদিন পর স্যারকে প্রথম ইমেইলের একটা কপি দিয়েছি। ছাত্র থাকা অবস্থায় কেন যেন ওইটা দিতে বা তাঁর লেখা ভাল লাগে এইটা বলা হয় নাই। স্যারের কোন ভাবান্তর নাই- বলরের আমি তো ঠিকই বলেছিলাম- দেখা তো হয়েছে।

কয়েকদিন আগে আমার শ্যালিকা ফোন করে বলে ভাইয়া আপনি দেখি মডেলিং শুরু করেছেন। যেটা জানলাম সেটা হল ৭ম শ্রেণীর তথ্য এবং যোগাযোগ প্রযুক্তি বইয়ে আমার শিক্ষক ডট কম এ দেয়া লেকচার সিরিজ থেকে একটা লেকচারের ছবি দেয়া হয়েছে। এত লেকচার থাকতে আমার লেকচার কেন আসল প্রথমে বুঝি নাই। ভেবেছিলাম random selection  এ আমারটা পড়ে গেছে। পরে জানলাম বইটা জাফর স্যারের লেখা। স্যার এতদিন পরেও আমাকে মনে রেখেছেন এবং খুঁজে আমার লেকচার বের করেছেন বইটার জন্য ভেবে খুবই আনন্দিত হয়েছি।

ওনার এবং ওনার বর্তমান সহকর্মীরা শাহজালাল বিশ্ববিদ্যালয়ে গবেষনা শুরু করেছেন এবং এটা থেকে দরকারী কার্যকর এখনই ব্যবহারযোগ্য প্রযুক্তি উদ্ভাবন হচ্ছে দেখে খুবই ভাল লাগে। যাদের গবেষনার অভিজ্ঞতা নাই (আমারও নাই) তাদের জন্য বলি একটা পেপার লেখা অনেক কঠিন। কিন্তু একটা প্রোটোটাইপ বানানো পেপার লেখা থেকে একশ গুন কঠিন। আর একটা ব্যবহারযোগ্য প্রযুক্তির উদ্ভাবন এবং সেটা  ব্যবহারযোগ্য করা হাজারগুন কঠিন। পত্রিকায় যদিও বড় শিরোনামে এগুলো দেখা যায় কিন্তু যারা পড়ে তার বেশিরভাগ মানুষের ধারণার বাইরে এরকম সিস্টেম বানানোর জন্য উন্নত দেশে কি পরিমান অর্থ ব্যয় হয়। এই বিষয়টা ওনার দেশে ফেরার পর সবচেয়ে বড় সাফল্য আমার মতে। জলমানব বইতে উনি মানুষের জীবনে ব্যবহার্য প্রযুক্তি নিয়ে বলেছেন যে এটাই সবচে বড় প্রযুক্তি। আমি নিজেও এই কথাটা বিশ্বাস করি। আমারিকা আসার আগে ওনার থেকে জলমানব বইটাতে একটা অটোগ্রাফ নিয়ে এসেছি। উনি নিজেও কথাটা বিশ্বাস করেন এটা জেনে অনেক ভাল লেগেছে।

আমি জলমানব বইটাতে দেয়া মুহম্মদ জাফর ইকবালের অটোগ্রাফ সুযোগ পেলেই সবাইকে দেখাই।