пользовательский распределитель памяти

Question

Я написал собственный распределитель памяти. У него есть 2 ограничения, которые я хочу удалить, поэтому он работает как malloc / free.

1.) Вызов mem_free требует приведения к беззнаковому символу * для его входного параметра. Я хотел бы взять указатель любого типа. Как это можно сделать?

2.) Распределитель памяти, который я написал, выделяет блок памяти перед буфером, а также записывает его размер. Функция free удаляет последний блок выделенной памяти в буфере. Так что порядок вызовов malloc / free имеет значение или не будет работать Как я могу снять это ограничение?

хочу иметь возможность сделать это:

char* ptr1 = mem_alloc(10);
char* ptr2 = mem_alloc(4);

mem_free(ptr1);
mem_free(ptr2);

должен сделать это сейчас:

char* ptr1 = mem_alloc(10);
char* ptr2 = mem_alloc(4);

mem_free(ptr2);
mem_free(ptr1);

Код:

unsigned char* mem_alloc(unsigned int size) {
    unsigned int s;
    if( (size + MEM_HEADER_SIZE)  > (MEM_MAX_SIZE - mem_current_size_bytes) ) {
        return NULL;
    }
    if(is_big_endian() == 0) {
        s = (mem_buff[3] << 24) + (mem_buff[2] << 16) + (mem_buff[1] << 8) + mem_buff[0];
    } else {
        s = (mem_buff[0] << 24) + (mem_buff[1] << 16) + (mem_buff[2] << 8) + mem_buff[3];
    }
    memcpy(mem_buff + mem_current_size_bytes, &size, sizeof(unsigned int));
    unsigned char* result = mem_buff + (mem_current_size_bytes + MEM_HEADER_SIZE);
    mem_current_size_bytes += MEM_HEADER_SIZE + size;
    return result;
}

void mem_free(unsigned char* ptr) {
    unsigned int i,s;
    for(i=0; i<mem_current_size_bytes; i++) {
        if( (char*)ptr == (char*)(mem_buff + i) ) {
            if(is_big_endian() == 0) {
                s = (*(ptr - 1) << 24) + (*(ptr - 2) << 16) + (*(ptr - 3) << 8) + *(ptr - 4);
            } else {
                s = (*(ptr - 4) << 24) + (*(ptr - 3) << 16) + (*(ptr - 2) << 8) + *(ptr - 1);
            }
            mem_current_size_bytes-=s;
            mem_current_size_bytes-=MEM_HEADER_SIZE;
            break;
        }
    }
}

Answer 1

1) Вместо этого используйте void *.
2) Хранить карту адресов для выделенных блоков и отдельную карту нераспределенных блоков. Затем вы можете посмотреть, какой блок освобождается на выделенной карте, удалить его и затем добавить блок на нераспределенную карту (убедившись, что он объединен с любыми свободными блоками по обе стороны от него). Конечно, это может привести к фрагментации памяти, но это действительно неизбежно.

Answer 2

Вы написали, что ищете идеи, поэтому я прилагаю один из моих проектов, которые я сделал в университете, в котором мы должны реализовать malloc () и free () ... Вы можете увидеть, как я это сделали, возможно, получить вдохновение или использовать все это, если хотите.Конечно, это не самая быстрая реализация, но она довольно проста и должна не содержать ошибок; -)

(обратите внимание, если кто-то из того же курса сталкивался с этим - пожалуйста, donне используйте это и скорее сделайте свой собственный - отсюда и лицензия; -)

/*
 * The 1st project for Data Structures and Algorithms course of 2010
 *
 * The Faculty of Informatics and Information Technologies at
 * The Slovak University of Technology, Bratislava, Slovakia
 *
 *
 * Own implementation of stdlib's malloc() and free() functions
 *
 * Author: mnicky
 *
 *
 * License: modified MIT License - see the section b) below
 *
 * Copyright (C) 2010 by mnicky
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * a) The above copyright notice and this permission notice - including the
 *    section b) - shall be included in all copies or substantial portions
 *    of the Software.
 *
 * b) the Software WILL NOT BE USED IN ANY WORK DIRECTLY OR INDIRECTLY
 *    CONNECTED WITH The Faculty of Informatics and Information Technologies at
 *    The Slovak University of Technology, Bratislava, Slovakia
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 */

#include <stdio.h>

typedef unsigned int MEMTYPE;

MEMTYPE *mem;
MEMTYPE memSize;
MEMTYPE avail;  //1st index of the 1st free range

//return size of block
MEMTYPE blockSize(MEMTYPE x) {
  return mem[x];
}

//return next free block
MEMTYPE next(MEMTYPE x) {
  return mem[x + mem[x]];
}

//return index of pointer to next free block
MEMTYPE linkToNext(MEMTYPE x) {
  return x + mem[x];
}

//initialize memory
void my_init(void *ptr, unsigned size) {

  mem = (MEMTYPE *) ptr;
  memSize = size / sizeof(MEMTYPE);
  mem[0] = memSize - 1;
  mem[memSize - 1] = memSize;
  avail = 0;
}

//allocate memory
void *my_alloc(unsigned size) {

  if (size == 0) {  //return NULL pointer after attempt to allocate 0-length memory
    return NULL;
  }

  MEMTYPE num = size / sizeof(MEMTYPE);
  if (size % sizeof(MEMTYPE) > 0) num++;
  MEMTYPE cur, prev;  //pointer to (actually index of) current block, previous block
  MEMTYPE isFirstFreeBeingAllocated = 1;  //whether the first free block is being allocated

  prev = cur = avail;

  //testing, whether we have enough free space for allocation
  test:

  if (avail == memSize) {  //if we are on the end of the memory
    return NULL;
  }

  if (blockSize(cur) < num) {  //if the size of free block is lower than requested
    isFirstFreeBeingAllocated = 0;
    prev = cur;

    if (next(cur) == memSize) {  //if not enough memory
      return NULL;
    }
    else
      cur = next(cur);
    goto test;
  }

  if (blockSize(cur) == num) {  //if the size of free block is equal to requested

    if (isFirstFreeBeingAllocated)
      avail = next(cur);
    else
      mem[linkToNext(prev)] = next(cur);
  }

  else {  //if the size of free block is greater than requested

    if (isFirstFreeBeingAllocated) {
      if ((blockSize(cur) - num) == 1)  //if there is only 1 free item left from this (previously) free block
        avail = next(cur);
      else
        avail = cur + num + 1;
    }
    else {
      if ((blockSize(cur) - num) == 1)  //if there is only 1 free item left from this (previously) free block
        mem[linkToNext(prev)] = next(cur);
      else
        mem[linkToNext(prev)] = cur + num + 1;
    }

    if ((blockSize(cur) - num) == 1)  //if there is only 1 free item left from this (previously) free block
      mem[cur] = num + 1;
    else {
      mem[cur + num + 1] = blockSize(cur) - num - 1;
      mem[cur] = num;
    }
  }

  return (void *) &(mem[cur+1]);
}

//free memory
void my_free(void *ptr) {

  MEMTYPE toFree;  //pointer to block (to free)
  MEMTYPE cur, prev;

  toFree = ((MEMTYPE *)ptr - (mem + 1));


  if (toFree < avail) {  //if block, that is being freed is before the first free block

    if (((linkToNext(toFree) + 1) == avail) && avail < memSize)  //if next free block is immediately after block that is being freed
      mem[toFree] += (mem[avail] + 1);  //defragmentation of free space
    else
      mem[linkToNext(toFree)] = avail;

    avail = toFree;
  }

  else {  //if block, that is being freed isn't before the first free block

    prev = cur = avail;

    while (cur < toFree) {
      prev = cur;
      cur = next(cur);
    }

    if ((linkToNext(prev) + 1) == toFree) { //if previous free block is immediately before block that is being freed

      mem[prev] += (mem[toFree] + 1);  //defragmentation of free space

      if (((linkToNext(toFree) + 1) == cur) && cur < memSize)  //if next free block is immediately after block that is being freed
        mem[prev] += (mem[cur] + 1);  //defragmentation of free space
      else
        mem[linkToNext(toFree)] = cur;
    }
    else {
      mem[linkToNext(prev)] = toFree;
      mem[linkToNext(toFree)] = cur;
    }

  }
}

Это было сделано, чтобы использовать как можно меньше места для метаинформации, поэтому выделенное пространство помечается номеромв 1-м узле выделенного диапазона, указывая количество следующих выделенных узлов.

Количество свободного пространства в свободном диапазоне обозначается числом, указывающим количество следующих за ним свободных узлов (включая этот узел) и последний узелсвободный диапазон содержит номер 1-го индекса следующего следующего свободного диапазона - что-то вроде этого (выделено красное пространство, белый свободен):

И это может бытьиспользуется так:

char region[30000000];  //space for memory allocation
my_init(region, 30000000);  //memory initialization

var = (TYPE *) my_alloc(sizeof(TYPE));  //memory allocation
my_free((void *) var);  //freeing the memory

Answer 3

Просто используйте указатель void * вместо char * в аргументе mem_free.

Для того, чтобы распределитель памяти работал с любой областью памяти, вам нужно добавить гораздо больше сложности ... Я бы порекомендовал изучить способ управления кучами памяти, и вы найдете несколько базовых схем, которые можно попробовать.

Answer 4

1. Вы должны переписать весь код.Распределители памяти обычно используют связанный список для хранения использованных и неиспользуемых фрагментов памяти, вы можете поместить эту ссылку в заголовок фрагмента перед размером.Я советую вам поискать несколько статей о том, как работают распределители памяти.Написание хорошо работающего распределителя памяти - это задача hard .