An Enhanced Allocator-C言語の動的メモリ割り当てにエラー・アラートを追加

19626 ワード

前言
このブログでは、C標準ライブラリの既存のmallocおよびfree関数を使用して、エラーアラートの機能を実現するより強力なダイナミックメモリディスペンサを作成します.
具体的なエラー警報機能の説明は、SSD 6 Exercise 3-Debugging Malloc Lab:Detecting Memory-Relatedのタイトル要件を参照してください.
基礎知識
背景
低レベルのmmapおよびmunmap関数を使用して仮想メモリの領域を作成および削除できますが、Cプログラマーは、実行時に追加の仮想メモリが必要な場合、ダイナミックメモリディスペンサ(dynamicmemory allocator)を使用すると便利であり、移植性も向上します.明示的なディスペンサ(explicit allocator)は、割り当てられたブロックを明示的に解放する必要がある.例えば、C標準ライブラリは、mallocパッケージと呼ばれる明示的なディスペンサを提供し、free関数を呼び出すことによってブロックを解放する.C++のnewおよびdeleteオペレータは、Cのmallocおよびfreeに相当します.
このブログでは、C標準ライブラリが提供するmallocおよびfree関数を使用して、エラーアラートの機能を実現するより強力なダイナミックメモリディスペンサを作成します.
次に、C標準ライブラリのmallocとfreeがそれぞれどのような機能を提供しているかを見てみましょう.
malloc

#include 
void *malloc(size_t size);

mallocのパラメータは、割り当てが必要なメモリバイト数であり、メモリプール内の使用可能なメモリがこの要件を満たすことができる場合、関数は、割り当てられたメモリブロックの開始位置を指すポインタを返す.
free

#include 
void free(void *pointer);

freeのパラメータは、NULLであるか、またはmalloc、callocまたはrealloc関数から以前に得られた戻り値である.freeパラメータをNULLに渡すと、何の効果も得られません.
けっかんぶんせき
動的メモリ分析では、次のようなエラーが頻繁に発生します.

NULLポインタを参照解除操作

割り当てられたメモリを操作するときに境界を越える

動的に割り当てられていないメモリを解放

動的割り当てメモリの一部を解放しようとする

ダイナミックメモリが解放された後も使用され続ける

私たちが見たように、C標準ライブラリに存在するmalloc、calloc、reallocとfreeの関数は、これらのエラーに対応するアラート処理を行わない.
そこで,Enhanced Allocatorを記述することによって,この欠陥を解決しようとした.
シナリオ設計
データ抽象
連続した仮想メモリスライス(chunk)を次の図に示します.

各chunkは、Header、Payload、Footerの3つの部分から構成されている.

Headerは、少なくとも以下の内容を含む.

checkSum (int):1つのchunkの一番前の部分は、checkSumの変化をチェックすることで、Headerが誤って変更されたかどうかを判断することができる.

size (size_t):Payloadのサイズ

filename (char *):ファイル名

linenum (int):行番号

Fence:は、特定の定数です.1つのchunkのHeaderとFooterのそれぞれに1つのFenceがあり、その値の変化をチェックすることで、Payloadの前方と後方が誤って変更されたか否かを判断することができる.

Payload:割り当てられるべきメモリブロック.

Footer:1つのFenceからなる.

エラー処理
私たちが完成したEnhanced Allocatorは、次の5つのエラーをキャプチャする予定です.
Error #1: Writing past the beginning of the user’s block (through the fence) Error #2: Writing past the end of the user’s block (through the fence) Error #3: Corrupting the header information Error #4: Attempting to free an unallocated or already-freed block Error #5: Memory leak detection (user can use ALLOCATEDSIZE to check for leaks at the end of the program)
データ構造
次に、具体的なデータ構造がどのように実現されるかを見てみましょう.
上記の5つのエラーをキャプチャするには、現在のプロセスで割り当てられているすべてのメモリスライスを維持(記録)し、メモリを解放するときにfreeのパラメータが有効かどうかを判断する必要があることがわかります.
では、最も簡単で、最も直接的な方法を採用して、1つの一方向チェーンテーブルを通じてすべての割り当てられたメモリスライスの記録を実現することができます.

/* Define Header */
struct header{
    int checkSum;
    size_t size;
    char *filename;
    int linenumber;
    struct header *next;  //           
};

具体的な実装では、FenceをHeaderから分離することで、メモリチップの設計をchunk = Header + Fence + Payload + Fenceに簡略化する.
具体的な実装
マクロ定義

#define FENCE_VALUE 0xCCDEADCC
#define BASIC_SIZE_HEADER sizeof(struct header) / 4
#define BASIC_SIZE_FENCE sizeof(FENCE_VALUE) / 4
#define BASIC_SIZE_META BASIC_SIZE_HEADER + BASIC_SIZE_FENCE * 2

我々は,1つのheader構造体からcheckSum,sizeなどの属性値を取得する際には,大量のポインタ増減操作(かつ整数ポインタの操作が多い)を行うため,上記マクロを定義することで,後続のコードをより明確かつ直感的にする.
上の4つのマクロ定義では、次のようになります.

FENCE_VALUE:取0xCCDEADCCこの定数

BASIC_SIZE_HEADER:構造体Headerの基本文字長

BASIC_SIZE_FENCE:定数FENCE_VALUEの基本ワード長

BASIC_SIZE_META:1つのメモリスライスに含まれるすべての追加情報の基本ワード長(chunk = Header + Fence + Payload + Fence,うちHeader,Fenceは追加情報)

たんほうこうチェーンテーブル

struct header *head_block = NULL;       //         
struct header *tail_block = NULL;       //        

/*       */
void initLinkedList(){
    if (head_block) {
        return;
    }

    head_block = malloc(sizeof(struct header));
    head_block->next = NULL;
    tail_block = head_block;
}

メモリスライスの割り当て操作は、チェーンテーブルの末尾に新しいノードを絶えず追加する必要があるため、末尾ノードによって割り当て操作が定数時間内に実行される.「削除(解放)されたノードがヘッダノードであるか否か」の判断を避けるため、テーブルヘッダノードを設定することで操作手順を簡略化できます.
取得META情報
メモリスライスHeadeの各プロパティ、前後の2つのFenceおよびPayloadの開始アドレスを総称して、そのMETA情報と呼ぶ.

int computeCheckSum(struct header *ptr) {
    return (ptr->size)|(ptr->linenumber);       //  size linenumber  checksum
}

int *getHeaderFenceOfChunk(struct header *ptr){
    return (int*)((int*)ptr + BASIC_SIZE_HEADER);
};

int *getFooterFenceOfChunk(struct header *ptr){
    return (int*)((int*)ptr + BASIC_SIZE_HEADER + BASIC_SIZE_FENCE + ptr->size/4);
};

void *getPayloadAddress(struct header *ptr){
    return ((int*)ptr + BASIC_SIZE_HEADER + BASIC_SIZE_FENCE);
};

注意:checkSumの定義には、ブロックサイズと行番号によってcheckSumを取得する方法を採用する様々な形式があります.MyMalloc()——ノードを追加

void *MyMalloc(size_t size, char *filename, int linenumber) {
    initLinkedList();

    struct header *new = malloc(BASIC_SIZE_META * 4 + size);
    new->size = size;
    new->filename = filename;
    new->linenumber = linenumber;
    new->checkSum = computeCheckSum(new);

    tail_block->next = new;
    tail_block = new;
    tail_block->next = NULL;

    *getHeaderFenceOfChunk(new) = FENCE_VALUE;
    *getFooterFenceOfChunk(new) = FENCE_VALUE;

    return getPayloadAddress(new);
}

MyFree()——ノードの削除
すべてのエラーアラート処理をMyfree()関数に配置します.つまり、メモリを解放する操作を実行するときにのみ、パラメータの妥当性を確認し、対応するエラープロンプトを行います.メモリの割り当て中にエラー・アラートはありません.
あるheaderパラメータについて、そのMETA情報を確認し、エラーコードを取得します.

/*        */
int getErrorCode(struct header *ptr){
    if(ptr == NULL){
        return 0;
    }else{
        int flag;

        flag = (*getHeaderFenceOfChunk(ptr) == FENCE_VALUE);
        if(!flag){      //Starting edge of the payload has been overwritten
            return 1;
        }

        flag = (*getFooterFenceOfChunk(ptr) == FENCE_VALUE);
        if(!flag){      //Ending edge of the payload has been overwritten
            return 2;
        }

        flag = (ptr->checkSum == computeCheckSum(ptr));
        if(!flag){      //Header has been corrupted
            return 3;
        }
    }
    return 0;
};

次に、MyFree()関数の具体的な実装を示します.

void MyFree(void *ptr, char *filename, int linenumber) {
    if (!head_block) {      //     
        error(4, filename, linenumber);
    }

    struct header *preFree = head_block;
    struct header *toFree = preFree->next;

    while (toFree) {        //            
        if(getPayloadAddress(toFree) == ptr){
            int errorCode = getErrorCode(toFree);
            if (errorCode) {
                errorfl(errorCode, toFree->filename, toFree->linenumber, filename, linenumber);
            }
            break;
        }else{
            preFree = toFree;
            toFree = preFree->next;
        }
    }

    if (!toFree) {      //   
        error(4, filename, linenumber);
    }

    /*       toFree   */
    preFree->next = toFree->next;
    free(toFree);
}

AllocatedSize()とPrintAllocatedBlocks()——ノード情報の取得AllocatedSize()関数は、現在割り当てられているすべてのメモリスライスのPayloadサイズの和を出力する必要があります.PrintAllocatedBlocks()関数は、割り当てられたメモリスライスのMETA情報を印刷する必要があります.したがって、この2つの関数は、実際には一方向チェーンテーブルを巡回しています.

/* returns number of bytes allocated using MyMalloc/MyFree:
    used as a debugging tool to test for memory leaks */
int AllocatedSize() {
    if (!head_block) {      //     
        return 0;
    }

    int sum = 0;
    struct header *temp = head_block->next;

    while (temp) {
        sum += temp->size;
        temp = temp->next;
    }

    return sum;
}

/* Prints a list of all allocated blocks with the
    filename/line number when they were MALLOC'd */
void PrintAllocatedBlocks() {
    if (!head_block) {      //     
        return;
    }

    struct header *temp = head_block->next;
    int sum = 0;

    while (temp) {
        printf("Allocated block %d: %d bytes, at line %d of the file %s.
",
               ++sum, temp->size, temp->linenumber, temp->filename);
        temp = temp->next;
    }
    return;
}

HeapCheck()——接点の点検を行う
前述したように、MyFree()関数が実行される場合にのみ、各メモリスライスのMETA情報が変更されているかどうかを判断するため、HeapCheck()関数が実現することを望んでいる機能は、この関数によって、現在の状態で、分配シートチェーンテーブルの各ノードが健康であるかどうかを直接見ることができることである.これももちろん遍歴操作です.

int HeapCheck() {
    int status = 0;
    if (!head_block) {      //     
        return status;
    }

    struct header *temp = head_block->next;

    while (temp) {
        int errorCode = getErrorCode(temp);
        if (errorCode) {
            status = -1;
            char *msg = getMsg(errorCode);
            printf("Error: %s
\tin block allocated at %s, line %d
",
                   msg, temp->filename, temp->linenumber);
        }
        temp = temp->next;
    }

    return status;
}

テストケース

static void run_test_case(int n) {
    switch(n) {
        case 1: { /* no error, just a basic test */
            char *str = (char *) MALLOC(12);
            strcpy(str, "123456789");
            FREE(str);
            printf("Size: %d
", AllocatedSize());
            PrintAllocatedBlocks();
        }
            break;
        case 2: { /* should overflow by 1 */
            char *str = (char *) MALLOC(8);
            strcpy(str, "12345678");
            FREE(str);
        }
            break;
        case 3: { /* should overflow by 1, harder to catch
                   because of alignment */
            char *str = (char *) MALLOC(2);
            strcpy(str, "12");
            FREE(str);
        }
            break;
        case 4: { /* memory leak */
            void *ptr = MALLOC(4), *ptr2 = MALLOC(6);
            FREE(ptr);
            printf("Size: %d
", AllocatedSize());
            PrintAllocatedBlocks();
        }
            break;
        case 5: {
            void *ptr = MALLOC(4);
            FREE(ptr);
            FREE(ptr);
        }
            break;
        case 6: {
            char *ptr = (char *) MALLOC(4);
            *((int *) (ptr - 8)) = 8 + (1 << 31);
            FREE(ptr);
            HeapCheck();
        }
            break;
        case 7: {
            char ptr[5];
            FREE(ptr);
        }
            break;
        case 8: {
            int i;
            int *intptr = (int *) MALLOC(6);
            char *str = (char *) MALLOC(12);

            for(i = 0; i < 6; i++) {
                intptr[i] = i;
            }
            if (HeapCheck() == -1) {
                printf("
Caught Errors
");
            }
        }
        default:
            ;
    }
}

8つの試験例は、上述したように、所望の出力を生成する.
case 1
case 2
case 3
case 4
case 5
case 6
case 7
case 8
参考資料
[1]『Cとポインタ』.[美]Kenneth A.reek著.[2]『コンピュータシステムを深く理解する』(第3版).Randal E.Bryant,David R.O’Hallaron著.

RxSwiftについてようやく理解できてきたのでまとめることにした(1)

RxSwift `a.withLatestFrom(a)` 同じ上流元の同期的合流問題