自定义分配器中的碎片。无法正确订购指针

Question

Context：我写了一个最适合的内存分配器。它分配大块内存，并根据请求将最适合的块提供给程序。如果内存用完了，它会要求OS提供更多信息。所有可用块均存储在链接列表中，并按增加指针值。]进行排序。

问题：

：释放内存时，程序应该将其链接回空闲块列表以进行回收，并且如果可能的话，更关键地将给定的块与其周围的块合并。不幸的是，只要我不需要让操作系统提供一个以上的超级块，这就可以很好地工作。当确实发生这种情况时，我收到的新块将具有无意义的寻址，并在其他超级块寻址空间之间插入。这导致永久性碎片。

Tl; dr

：我得到了新的存储器超级块，其地址在另一个超级块的地址空间内，导致在返回子块时产生碎片。

问题的说明

：这里是我上面描述的问题的图表。

数字：内存地址（来自实际执行）。>
• 米色块：可用内存。
• 白块：内存未链接使用。
• 该图显示了内存使用的进程，直到发生碎片催化剂为止。您可以看到，一旦插入了块，一旦将它们重新签入，就永远不可能合并繁忙的块。

代码：可复制示例：以下内容包括分配器和一个小型测试程序。必须至少使用C99进行编译。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*****************************************************************************/
/*                          SYMBOLIC CONSTANTS                               */
/*****************************************************************************/

#define NEXT(hp)                ((hp)->key.next)
#define UNITS(hp)               ((hp)->key.units)
#define UNIT_SIZE               sizeof(Header)

#define MIN_UNITS_ALLOC         64
#define MAX(a,b)                ((a) > (b) ? (a) : (b))

/*****************************************************************************/
/*                          TYPE DEFINITIONS                                 */
/*****************************************************************************/

typedef union header {
    intmax_t align;
    struct {
        union header *next;
        unsigned units;
    } key;
} Header;

/*****************************************************************************/
/*                          GLOBAL VARIABLES                                 */
/*****************************************************************************/

Header base = {.key = { NULL, 0 }};
Header *list;

/*****************************************************************************/
/*                              PROTOTYPES                                   */
/*****************************************************************************/

/* Allocates a 'bytes' size block of memory. On success, returns pointer to
 * the block. On error, NULL is returned. */
void *alloc (size_t bytes);

/* Returns a 'bytes' size block of allocated memory for reuse */
void release (void *bytes);

/* Attempts to reserve memory from the operating system via a system call */
static Header *reserve (unsigned units);

/*****************************************************************************/
/*                      FUNCTION IMPLEMENTATIONS                             */
/*****************************************************************************/


void *alloc (size_t bytes) {
    size_t units, diff;
    Header *block, *lastBlock, *best, *lastBest;

    if (bytes == 0) {
        return NULL;
    }

    if (list == NULL) {
        list = base.key.next = &base;
    }

    best = lastBest = NULL;
    units = (bytes + UNIT_SIZE - 1) / UNIT_SIZE + 1;
    diff = SIZE_MAX;

    for (lastBlock = list, block = NEXT(list); ; lastBlock = block, block = NEXT(block)) {

        /* Loop across list, find closest fitting block */
        if (UNITS(block) >= units && UNITS(block) - units < diff) {
            diff = UNITS(block) - units;
            best = block;
            lastBest = lastBlock;
        }

        /* Upon cycle completion */
        if (block == list) {

            /* If no block available, reserve some. */
            if (best == NULL) {
                if ((lastBest = reserve(units)) == NULL) {
                    return NULL;
                } else {
                    fprintf(stderr, "\nalloc: Out of memory, linking new block %lld of size %u.\n\n", (long long)lastBest, UNITS(lastBest));
                    release((void *)(lastBest + 1));
                }

            /* If block of perfect size, return. Else slice and return */
            } else {
                if (diff == 0) {
                    NEXT(lastBest) = NEXT(best);
                } else {
                    UNITS(best) = diff;
                    best += diff;
                    UNITS(best) = units;
                }
                fprintf(stderr, "alloc: Unlinked block %lld of %u units.\n", (long long)best, UNITS(best));
                return (void *)(best + 1);
            }
        }
    }
}

void release (void *bytes) {
    Header *p, *block;

    block = (Header *)bytes - 1;

    /* Choose p such that: p -> block -> NEXT(p) */
    for (p = list; !(p < block && NEXT(p) > block); p = NEXT(p)) {
        if (p >= NEXT(p) && (block > p || block < NEXT(p))) {
            break;
        }
    }

    /* Merge block with NEXT(p) if adjacent */
    if (block + UNITS(block) == NEXT(p)) {
        NEXT(block) = NEXT(NEXT(p));
        UNITS(block) += UNITS(NEXT(p));
    } else {
        NEXT(block) = NEXT(p);
    }

    /* Merge block with p if adjacent */
    if (p + UNITS(p) == block) {
        NEXT(p) = NEXT(block);
        UNITS(p) += UNITS(block);
    } else {
        NEXT(p) = block;
    }

}

static Header *reserve (unsigned units) {
    char *bytes, *sbrk(int);
    Header *block;
    units = MAX(units, MIN_UNITS_ALLOC);

    if ((bytes = sbrk(units)) == (char *)-1) {
        return NULL;
    } else {
        block = (Header *)bytes;
        UNITS(block) = units;
    }
    return block;
}

/*****************************************************************************/
/*                      TESTING FUNCTIONS (DELETE)                           */
/*****************************************************************************/


void printFreeList (unsigned byAddress) {
    Header *lp = list;

    if (lp == NULL) {
        fprintf(stdout, "List is NULL\n");
        return;
    }

    do {
        fprintf(stdout, "[ %lld ] -> ", (byAddress ? (long long)lp : (long long)UNITS(lp)));
        lp = NEXT(lp);
    } while (lp != list);
    putc('\n', stdout);
}

void releaseItemAtIndex (int i, int k, long long *p[]) {
    fprintf(stderr, "Releasing block %d/%d\n", i, k);
    release(p[i]);
    for (int j = i; j < k; j++) {
        if (j + 1 < k) {
            p[j] = p[j + 1];
        }
    }
}

#define MAX_TEST_SIZE           5000

int main (int argc, const char *argv[]) {

    /* Seed PRNG: For removed random deletion (now manual) */
    srand(time(NULL));

    /* Array of pointers to store allocated blocks, blockSize we want to allocate. */
    long long *p[MAX_TEST_SIZE], blockSize = 256;

    /* Number of blocks we choose to allocate */
    int k = 6;

    /* Allocate said blocks */
    for (int i = 0; i < k; i++) {
        p[i] = alloc(blockSize * sizeof(char));
        printFreeList(0); printFreeList(1); putchar('\n');
    }

    fprintf(stderr, "\n\n");

    int idx;
    while (k > 0) {
        fprintf(stderr, "Delete an index between 0 up to and including %d:\n", k - 1);
        scanf("%d", &idx);
        releaseItemAtIndex(idx, k, p);
        printFreeList(0); printFreeList(1); putchar('\n');
        k--;
    }

    return 0;
}

其他详细信息

：

我正在运行64位操作系统。
• 我不知道是否保证堆上的指针比较有效。根据K＆R，此标准不能保证。

上下文：我已经写了一个最适合的内存分配器。它分配大块内存，并根据请求将最适合的块提供给程序。如果内存用完了，它会要求...

好吧，我最终在几年后写了这篇文章，看来还不错。奖励：它使用静态内存。

---

头文件

#if !defined(STATIC_ALLOCATOR_H)
#define STATIC_ALLOCATOR_H


/*
 *******************************************************************************
 *                        (C) Copyright 2020                                   *
 * Created: 07/04/2020                                                         *
 *                                                                             *
 * Programmer(s):                                                              *
 * - Jillian Oduber                                                            *
 * - Charles Randolph                                                          *
 *                                                                             *
 * Description:                                                                *
 *  Static first-fit memory allocator                                          *
 *                                                                             *
 *******************************************************************************
*/


#include <iostream>
#include <cstddef>
#include <cstdint>
#include "dx_types.h"

extern "C" {
    #include "stddef.h"
}


/*
 *******************************************************************************
 *                              Type Definitions                               *
 *******************************************************************************
*/


// Defines the header block used in the custom allocator
typedef union block_h {
    struct {
        union block_h *next;
        size_t size; // Size is in units of sizeof(block_h)
    } d;
    max_align_t align;
} block_h;



/*
 *******************************************************************************
 *                              Class Definitions                              *
 *******************************************************************************
*/


class Static_Allocator {
public:


    /*\
     * @brief Configures the class with the given static memory capacity
     * @param memory Pointer to static array (must support address comparison)
     * @param size   Total number of bytes alloted for distribution
    \*/
    Static_Allocator(uint8_t *memory, size_t size);

    /*\
     * @brief Returns a memory block of the desired size
     * @param size Number of bytes to allocate
     * @return 
     *  - valid pointer if memory is available
     *  - NULL otherwise
    \*/
    uint8_t *alloc (size_t size);


    /*\
     * @brief Releases the allocated block of memory
     * @param ptr Pointer to allocated block of memory
     * @return 
     *  - STATUS_OK on success
     *  - STATUS_ERR if invalid block 
     *  - STATUS_BAD_PARAM on NULL parameter
    \*/
    dx::status_t free (uint8_t *ptr);


    /*\
     * @brief Returns the amount of free memory
     * @return size_t Bytes (of available free memory)
    \*/
    size_t free_memory_size ();


    /*\
     * @brief Debug utility which shows what is on the free-list
     * @return None
    \*/
    void show ();

    /*\
     * @brief Debug utility which asserts there is only a single
     *        memory block
    \*/
    bool unified ();


private:

    // Fixed allocator capacity 
    size_t d_capacity;

    // Fixed memory 
    uint8_t *d_memory;

    // Pointer to head of the linked list
    block_h *d_free_list;

    // Available memory
    size_t d_free_memory_size;

    // Unit size
    static const size_t mem_unit_size = sizeof(block_h);

};


#endif

源文件
#include "static_allocator.h"


Static_Allocator::Static_Allocator (uint8_t *memory, size_t size):
    d_capacity(0),
    d_memory(NULL),
    d_free_list(NULL),
    d_free_memory_size(0)
{
    // Assign memory array
    d_memory = memory;

    // Trim off two mem_unit_size for head + init-block + spillover
    d_capacity = size - (size % mem_unit_size) - 2 * mem_unit_size;

    // Ensure free memory is set to capacity
    d_free_memory_size = d_capacity;
}


uint8_t * Static_Allocator::alloc (size_t size)
{
    block_h *last, *curr;

    // Number of blocks sized units to allocate
    size_t nblocks = (size + mem_unit_size - 1) / mem_unit_size + 1;

    // If larger than total capacity or invalid size; immediately return
    if ((nblocks * sizeof(block_h)) > d_capacity || size == 0) {
        return NULL;
    }

    // If uninitialized, create initial list units
    if ((last = d_free_list) == NULL) {
        block_h *head = reinterpret_cast<block_h *>(d_memory);
        head->d.size = 0;

        block_h *init = head + 1;
        init->d.size = d_capacity / sizeof(block_h);
        init->d.next = d_free_list = last = head;

        head->d.next = init;
    }

    // Problem: You must not be allowed to merge the init block

    // Look for space - stop if wrapped around
    for (curr = last->d.next; ; last = curr, curr = curr->d.next) {

        // If sufficient space available
        if (curr->d.size >= nblocks) {

            if (curr->d.size == nblocks) {
                last->d.next = curr->d.next;
            } else {
                curr->d.size -= nblocks;
                curr += curr->d.size; // Suspect
                curr->d.size = nblocks;
            }

            // Reassign free list head
            d_free_list = last;

            // Update amount of free memory available
            d_free_memory_size -= nblocks * sizeof(block_h);

            return reinterpret_cast<uint8_t *>(curr + 1);
        }

        // Otherwise not sufficient space. If reached
        // the head of the list again, there is no more
        // memory left
        if (curr == d_free_list) {
            return NULL;
        }
    }
}


dx::status_t Static_Allocator::free (uint8_t *ptr)
{
    block_h *b, *p;

    // Check if parameter is valid
    if (ptr == NULL) {
        std::cerr << "Null pointer!";
        return dx::STATUS_BAD_PARAM;
    }

    // Check if memory is in range
    if (!(ptr >= (d_memory + 2 * mem_unit_size) 
        && ptr < (d_memory + d_capacity + 2 * mem_unit_size))) {
        std::cerr << "Pointer out of range!";
        return dx::STATUS_ERR;
    }

    // Obtain block header (ptr - sizeof(block_h))
    b = reinterpret_cast<block_h *>(ptr) - 1;


    // Update available memory size
    d_free_memory_size += b->d.size; 

    // Find insertion location for block
    for (p = d_free_list; !(b >= p && b < p->d.next); p = p->d.next) {

        // If the block comes at the end of the list - break
        if (p >= p->d.next && b > p) {
            break;
        }

        // If at the end of the list, but block comes before next link
        if (p >= p->d.next && b < p->d.next) {
            break;
        }
    }

    // [p] <----b----> [p->next] ----- [X]

    // Check if we can merge forwards
    if (b + b->d.size == p->d.next) {
        b->d.size += (p->d.next)->d.size;
        b->d.next = (p->d.next)->d.next;
    } else {
        b->d.next = p->d.next;
    }

    // Check if we can merge backwards
    if (p + p->d.size == b) {
        p->d.size += b->d.size;
        p->d.next = b->d.next;
    } else {
        p->d.next = b;
    }

    d_free_list = p;

    return dx::STATUS_OK;
}


size_t Static_Allocator::free_memory_size () 
{
    return d_free_memory_size;
}


void Static_Allocator::show ()
{
    std::cout << "Block Size: " << sizeof(block_h) << "\n"
         << "Capacity: " << d_capacity << "\n"
         << "Free Size (B): " << d_free_memory_size << "\n";

    if (d_free_list == NULL) {
        std::cout << "<uninitialized>\n";
        return;
    }

    // Show all blocks
    block_h *p = d_free_list;
    do {
        std::cout << "-------------------------------\n";
        std::cout << "Block Address: " << (uint64_t)(p) << "\n";
        std::cout << "Blocks (32B): " << p->d.size << "\n";
        std::cout << "Next: " << (uint64_t)(p->d.next) << "\n";
        std::cout << "{The next block is " << (uint64_t)((p->d.next) - (p)) << " bytes away, but we claim the next " << p->d.size * mem_unit_size << " bytes\n";
        p = p->d.next;
    } while (p != d_free_list);
    std::cout << "-------------------------------\n\n\n";
}


bool Static_Allocator::unified () {
    if (d_free_list == NULL) {
        return false;
    }
    return ((d_free_list->d.next)->d.next == d_free_list);
}

Answer 1

好吧，我最终在几年后写了这篇文章，看来还不错。奖励：它使用静态内存。