Dynamic memory কেন: যে মাপটা আগে থেকে জানা নেই

Module 9-এর project-এ Amara-র marks report পুরো ক্লাসটা রাখত int marks[MAX_S][MAX_M]-এ, আর MAX_S ছিল 100। 101 জন ছাত্রের একটা sheet দিলে ফেরত আসত মাত্র দুইটা শব্দ: invalid size।

এবার অফিস বলছে না ক্লাসে কতজন। Sheet-এর প্রথম লাইনে সংখ্যাটা থাকবে, আর সেটা 12-ও হতে পারে, 3,000-ও হতে পারে।

Array-র মাপ ঠিক হয়ে যায় program compile হওয়ার আগেই, অথচ এই সংখ্যাটা আসে input-এর সাথে। এই lesson সংখ্যাটা জানার পরেই বাক্সগুলো চেয়ে নেয়।

যে মাপ আগে থেকে জানা নেই, তার তিনটা উত্তর

প্রথম দুইটা উত্তর Module 9-এর, তৃতীয়টা এই module-এর।

Constant নিজের সীমা নিয়ে সৎ, আর সমস্যাটা ওই সীমাতেই। যেদিন স্কুল দুইটা ক্লাস এক করে দেবে, সেদিন program আসল data-ই ফিরিয়ে দেবে।

বিশাল static array-র খরচ দেখতে যতটা, আসলে ততটা না। Module 9-এর lesson 3 Playground-এ 280 MB-র একটা static array মেপেছিল, আর সেটা pass করেছিল মাত্র 416 KB খরচ করে। Operating system memory দেয় 4,096 byte-এর এক একটা page ধরে, আর একটা page গোনে তখনই, যখন program প্রথমবার ওটা ছোঁয়। তাই আসল খরচ হলো থেকে যাওয়া ছাদটা, আর এমন একটা program, যেটা "যতজনই হোক" বোঝাতে লেখে "দশ লাখ"।

malloc n read করার পরে ঠিক n-টা বাক্স চায়, code-এ কোনো ছাদ লেখা থাকে না। বদলে আসে দুইটা নতুন দায়িত্ব: যা ফেরত এল সেটা check করা, আর কাজ শেষে block-টা ফেরত দেওয়া।

তাই constant আর static array দুটোই ছাদটা বেঁধে দেয় compile-এর সময়, আর malloc মাপটা ঠিক করে program চলার সময়।

Heap: Module 11 যে box-টা dashed এঁকেছিল

Module 7-এর lesson 5 memory-র তৃতীয় একটা জায়গার কথা দিয়েছিল, আর Module 11-এর lesson 1 ওটা এঁকেছিল dashed একটা box হিসেবে, গায়ে লেখা Module 14। এটাই heap: memory-র একটা এলাকা, যেখান থেকে program চলার সময় টুকরো টুকরো করে জায়গা চেয়ে নেয়।

চেয়ে নেওয়াকে বলে allocate করা, আর একটা টুকরোকে বলে block: পাশাপাশি বসানো কিছু byte, নাম ছাড়া একটা array-র মতো। এভাবে সামলানো memory-কে বলে dynamic memory, কারণ ওর মাপ আর আয়ু দুটোই ঠিক হয় program চলার সময়।

একটা block-এ পৌঁছাও একটা pointer দিয়ে, যেটা ওর address ধরে রাখে, আর ওই pointer একটা সাধারণ local। ছবিতে marks বসে আছে stack-এ, main-এর frame-এ, আর ও যে পাঁচটা বাক্স দেখাচ্ছে সেগুলো আছে heap-এ।

Program যত চায়, heap তত উপরের দিকে বাড়ে, আর stack বাড়ে নিচের দিকে (Module 8-এর lesson 2)। C library heap-টা কীভাবে বড় করে, সেটা দেখাবে lesson 6।

একটা local মারা যায় ওর function-এর closing brace-এ। একটা block থাকে যতক্ষণ না program ওটার উপর free call করে, তাই একটা function block allocate করে ওর address return করতে পারে। Example 2 ঠিক এটাই করে।

তাই pointer-টা stack-এর একটা local, আর ও যে বাক্সগুলো দেখায় সেগুলো heap-এ থাকে, যতক্ষণ না তুমি free করো।

malloc, অংশ ধরে ধরে পড়া

malloc ("memory allocate"-এর ছোট রূপ) আসে <stdlib.h> থেকে। ও নেয় কয় byte লাগবে, আর return করে একটা নতুন block-এর প্রথম byte-এর address। Block দিতে না পারলে return করে NULL।

int *marks = malloc(n * sizeof *marks);

sizeof(int) কেন না? এখানে দুটোই 4 দেয়। কিন্তু পরে marks যদি long long * হয়ে যায়, sizeof *marks নিজে থেকেই 8 হয়ে যাবে। sizeof(int) থেকে যাবে 4, আর block হবে দরকারের অর্ধেক। বন্ধনী লাগে শুধু type-এর নামের চারপাশে।

পুরো idiom-টা দেখো Amara-র program-এ, যেটা প্রথম আর শেষ নম্বরটা print করে।

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n = 0;
    int *marks = NULL;

    if (scanf("%d", &n) != 1 || n < 1) {
        printf("no marks\n");
        return 0;
    }
    marks = malloc(n * sizeof *marks);
    if (marks == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &marks[i]);
    }
    printf("students: %d\n", n);
    printf("first mark: %d, last mark: %d\n", marks[0], marks[n - 1]);
    free(marks);
    return 0;
}

students: 5
first mark: 90, last mark: 51

ওই output-টা input 5, তারপর 90 72 64 88 51-এর জন্য। n = 5 হলে call-টা চায় 5 × 4 = 20 byte। কোনো command line-এই কোনো বার্তা নেই: Playground, -Wall আর -Wall -Wextra, সবাই চুপ।

তাই malloc(n * sizeof *marks) জোরে পড়লে দাঁড়ায়: "n-টা বাক্স, প্রতিটা marks যে বাক্স দেখায় তার মাপের।"

উত্তরটা check করো: NULL, আর Playground-এ কী fail করে

malloc block দিতে না পারলে return করে NULL, সেই pointer যেটা কোথাও দেখায় না (Module 11-এর lesson 2)। NULL দিয়ে write করা undefined behaviour, তাই এই track প্রতিটা allocation-এর ঠিক পরের লাইনেই check করে। main-এ check-টা stderr-এ out of memory print করে 1 return করে।

এমনটা কত ঘন ঘন হয়? তুমি যা ভাবছ তার চেয়ে কম। Live Playground-এ মেপে দেখা গেছে, যেখানে memory limit 256,000 KB:

বাংলা page-এ এই দুইটা badge বাংলায় লেখা থাকে।

তাই malloc দেয় address-এর জায়গা, memory না। Limit শুধু সেই page-গুলো গোনে যেগুলো program ছোঁয়, ঠিক যে নিয়মে Module 9-এর static array pass করেছিল। Limit-এর অনেক বেশি চাইলেও pointer পাওয়া যায়, আর run থামে তখন, যখন program বেশি জায়গায় লিখে ফেলে। NULL এসেছে শুধু সেই request-এ, যেটা মেশিন সোজা না করে দিয়েছে; সীমাটা মেশিনভেদে সরে যায়, যেমন Compiler Explorer-এ 12 GB-তে pointer এসেছে, আর 16 GB-তে NULL।

তাহলে check কেন? কারণ কিছু request সত্যিই fail করে, আর তার একটা ভুল করে বানিয়ে ফেলা খুব সহজ। Zara অদ্ভুত input দিয়েই আগে test করে, তাই ও এই program-কে দেয় -1।

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n = 0;
    int *marks = NULL;

    if (scanf("%d", &n) != 1) {
        return 1;
    }
    marks = malloc(n * sizeof *marks);
    if (marks == NULL) {
        printf("malloc returned NULL for n = %d\n", n);
        return 1;
    }
    printf("got a block for n = %d\n", n);
    free(marks);
    return 0;
}

কোনো command line-এই কোনো বার্তা নেই। Live Playground-এ মেপে দেখা গেছে, run print করেছে malloc returned NULL for n = -1, আর return 1; দেখিয়েছে Runtime error (বাংলা page-এ badge-টা বাংলায় লেখা থাকে), সাথে Exit: 1। sizeof দেয় unsigned একটা size_t, তাই -1 ঘুরে গিয়ে হয়ে যায় সবচেয়ে বড় size_t। 4 দিয়ে গুণ করলে সেটা 18,446,744,073,709,551,612 byte।

-1-টা যদি input থেকে না এসে program-এই লেখা থাকে, GCC 12 compile করার সময়ই মাপটা দেখতে পায়। Playground সেটা দেখায় amber রঙের Compile output tab-এ: warning: argument 1 value '18446744073709551612' exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]। Input থেকে read করলে একই ভুলে কোনো সাড়াশব্দ নেই, তাই n check করার দায়িত্ব program-এর নিজের।

এজন্যই উপরের Amara-র program আগে n < 1 পরীক্ষা করে: -1 বা 0 পেলে ও print করে no marks, আর malloc call-ই করে না। NULL check-টাও থাকে, কম জায়গার মেশিনের জন্য, আর মাসের পর মাস ধরে চাইতে থাকা program-এর জন্য। যে program ধরে নেয় malloc কখনো fail করে না, সে এখনো Zara-র পাল্লায় পড়েনি।

তাই allocate করার আগে n check করো, আর পরে pointer-টা।

Block-টা array-র মতো ব্যবহার করো, তারপর free করো

Check পার হলে block-টা ঠিক একটা array-র মতোই ব্যবহার হয়। marks[i] মানে *(marks + i) (Module 11-এর lesson 3): block-এর address থেকে শুরু করো, i বাক্স এগোও, আর সেখানকার বাক্সটা ব্যবহার করো। Index চলে 0 থেকে n - 1 পর্যন্ত, যেকোনো array-র মতোই, আর কেউ তোমার হয়ে সেটা check করে না।

কাজ শেষ হলে free(marks) block-টা ফেরত দেয় allocator-কে, মানে C library-র সেই অংশকে যেটা block বিলি করে। এরপর marks একটা dangling pointer (Module 11-এর lesson 7): ওতে একটা address আছে ঠিকই, কিন্তু block-টা আর তোমার না। যে pointer পরেও ব্যবহার হবে, তার জন্য lesson 2 যোগ করবে marks = NULL;; ঠিক return-এর আগে শুধু free-ই যথেষ্ট।

যে block-কে আর কেউ দেখায় না, অথচ কখনো free করা হয়নি, সেটা একটা leak। Leak output-এ কিছুই বদলায় না। Program শেষ হলে operating system ওর সব page ফেরত নিয়ে নেয়। তাই Playground-এ একটা free বাদ পড়লে চোখে পড়ার মতো কোনো ক্ষতি হয় না।

তবুও অভ্যাসটা জরুরি, কারণ সব program শেষ হয় না। একটা web server মাসের পর মাস চলে, আর প্রতিটা request-এর জন্য allocate করে। প্রতিটা request যদি একটা করে block leak করে, ওর memory বাড়তেই থাকে, যতক্ষণ না মেশিন আর দিতে রাজি হয়; এমন একটা leak মেপে দেখাবে lesson 5। তাই এই track প্রতিটা block free করে প্রতিটা পথে, আগেভাগে return করা পথগুলোসহ।

তাই block-টা array-র মতো index করো, আর program থেকে বের হওয়ার প্রতিটা পথে free করো।

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *scores = malloc(3 * sizeof *scores);

    if (scores == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    scores[0] = 70;
    scores[1] = 85;
    scores[2] = 91;
    printf("Kenji's scores: %d %d %d\n", scores[0], scores[1], scores[2]);
    free(scores);
    return 0;
}

Kenji's scores: 70 85 91

#include <stdio.h>
#include <stdlib.h>

#define PASS_MARK 40

int *read_marks(int n);
int count_passed(const int *marks, int n);

int main(void)
{
    int n = 0;
    int *marks = NULL;

    if (scanf("%d", &n) != 1 || n < 1) {
        printf("no marks\n");
        return 0;
    }
    marks = read_marks(n);
    if (marks == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    printf("passed: %d of %d\n", count_passed(marks, n), n);
    for (int i = 0; i < n; i++) {
        if (marks[i] < PASS_MARK) {
            printf("needs help: student %d with %d\n", i + 1, marks[i]);
        }
    }
    free(marks);
    return 0;
}

int *read_marks(int n)
{
    int *marks = malloc(n * sizeof *marks);

    if (marks == NULL) {
        return NULL;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &marks[i]);
    }
    return marks;
}

int count_passed(const int *marks, int n)
{
    int passed = 0;

    for (int i = 0; i < n; i++) {
        if (marks[i] >= PASS_MARK) {
            passed = passed + 1;
        }
    }
    return passed;
}

passed: 4 of 6
needs help: student 2 with 35
needs help: student 6 with 22

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n = 0;
    int *prices = NULL;
    int total = 0;

    if (scanf("%d", &n) != 1 || n < 1) {
        printf("empty receipt\n");
        return 0;
    }
    prices = malloc(n * sizeof *prices);
    if (prices == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &prices[i]);
        total = total + prices[i];
    }
    printf("receipt: %d items, total %d\n", n, total);
    for (int i = 0; i < n; i++) {
        printf("  item %d: %d\n", i + 1, prices[i]);
    }
    free(prices);
    return 0;
}

receipt: 3 items, total 285
  item 1: 65
  item 2: 180
  item 3: 40

#include <stdio.h>

int main(void)
{
    int n = 5;
    int *marks = malloc(n * sizeof *marks);

marks = malloc(n);
if (marks == NULL) {
    fprintf(stderr, "out of memory\n");
    return 1;
}

for (int i = 0; i <= n; i++) {
    total = total + prices[i];
}

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *marks = malloc(0);

    if (marks == NULL) {
        printf("malloc(0) gave NULL\n");
    } else {
        printf("malloc(0) gave a pointer\n");
    }
    free(marks);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int *read_marks(int n);
void print_report(const int *marks, int n);

int main(void)
{
    int n = 0;
    int *marks = NULL;

    scanf("%d", &n);
    marks = read_marks(n);
    if (n > 0 && marks == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    print_report(marks, n);
    free(marks);
    return 0;
}

int *read_marks(int n)
{
    /* Ask malloc for exactly n boxes, check the answer for NULL,
       read n marks into the boxes and return the block. */
    return NULL;
}

void print_report(const int *marks, int n)
{
    /* Print "mean: X.XX" and "max: M" on two lines, or "no marks" when n is 0. */
}

#include <stdio.h>
#include <stdlib.h>

long long *make_squares(int n);

int main(void)
{
    int n = 0;
    long long *squares = NULL;
    long long sum = 0;

    scanf("%d", &n);
    squares = make_squares(n);
    if (n > 0 && squares == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    /* Print box 0 to box n - 1, one per line, and add each one to sum. */
    printf("sum: %lld\n", sum);
    free(squares);
    return 0;
}

long long *make_squares(int n)
{
    /* For n = 0, allocate nothing and return NULL. Otherwise ask malloc
       for exactly n boxes, check for NULL, and put (i + 1) squared in box i. */
    return NULL;
}

এরপর Bob একটা block বড় করতে যায়, আর যে একটা run-এ realloc না বলে দেয়, ঠিক সেখানেই block-টা হারায়। Lesson 2 খোলে চারটা call, malloc, calloc, realloc আর free, আর মেপে দেখায় কোনটা কী কথা দেয়।