Распределитель памяти в C как использовать пространство sbrk () 'ed

Я писал реализацию malloc и мне было интересно, может ли кто-нибудь помочь мне с этой проблемой.

По сути, я хотел бы повторно использовать память после выделения ее с помощью sbrk () и убедившись, что память свободна.

Итак, по сути, представьте, что моя память такая

|------------------------------|

... и я делаю некоторые распределения. Когда я выделяю память, каждый бит имеет заголовок (h) и данные (d).

|hddddddhddd---hdd--hddd-------|

Теперь у меня есть эти отверстия, и если я хочу использовать, скажем, первый пробел в моей диаграмме, как мне настроить его так, чтобы у него также была голова (h) и тело (dd)?

Я дошел до того, что теперь у меня есть указатель на нужное место в памяти. В C на него указывает указатель. Указатель имеет настраиваемый тип, где «мета» - это определенная мной структура. Итак, теперь у меня есть

metaStruct * mypointer = the memory address.

Но когда я пытаюсь сделать

mypointer->size = 30;

Or

mypointer->buddy = 1;

Я получаю ошибку.

Вопрос: как мне настроить так, чтобы адрес памяти, выделенный с помощью sbrk (), имел форму моей структуры? Очевидно, я не могу просто использовать myPointer = malloc (sizeof (metaStruct)), потому что я пишу сам malloc. Я также не заинтересован в том, чтобы sbrk () занимал больше места, а скорее использовал существующее пространство, на которое я указываю (я хочу игнорировать его ненужные данные и использовать пространство).

Как мне это сделать?


person Navin Aggrawal    schedule 26.03.2011    source источник
comment
Между прочим, многие новые malloc(3) реализации вызывают mmap(2) с MAP_ANONYMOUS, чтобы выделить новые обнуленные страницы для процесса. Поскольку выделения могут быть такими маленькими, как размер страницы, и могут быть возвращены в ОС в любом порядке, легче вернуть память в ОС из процесса. И может быть проще выделить новые страницы для хранения ваших собственных внутренних структур данных.   -  person sarnold    schedule 26.03.2011
comment
Спасибо, sarnold - мне известно о mmap, но я делаю это в учебных целях. С моей реализацией sbrk () мне было только интересно, нужно ли мне явно настраивать что-то для использования памяти, на которую ссылается указатель? Типа мемсет или что-то в этом роде. Я просто хочу решить эту проблему, ха-ха. Я уже зашел так далеко, что нет смысла начинать заново: D   -  person Navin Aggrawal    schedule 26.03.2011
comment
Я не могу с этим спорить! :) Удачного взлома.   -  person sarnold    schedule 26.03.2011
comment
спасибо, сарнольд. теперь интересно, кто знает, как это решить ...   -  person Navin Aggrawal    schedule 26.03.2011


Ответы (1)


Насколько мне известно, p = sbrk (n) увеличивает доступное адресное пространство (как минимум) на n байтов и возвращает базовый адрес новой выделенной области в «p». Итак, теперь у вас есть блок памяти, начинающийся с «p» и длиной n байтов (возможно, больше, чем n, это зависит от системы).

Итак, я предполагаю, что ваш «metaStruct» содержит поле «размер», поле «следующая свободная область» и поле «данные»,

metaStruct * m ;
p=sbrk(sizeof(metaStruct)+ data_size);
m = (metaStruct *)p;
m->size = data_size;
m->next = NULL;
memcpy(m->data, ...,data_size);

Код не идеален, в некоторых системах функция sbrk (действительно, часто это функция, а не базовый системный вызов - и, конечно, вы должны проверить, не работает ли sbrk) не возвращает выровненные указатели, поэтому вам нужно выровнять указатель вручную . Кроме того, вы можете получить фактический выделенный размер, вызвав sbrk (0) после sbrk (n) и вычислив разницу между двумя указателями. В общем, вы должны поддерживать набор «свободных блоков» и пытаться использовать их сначала, а затем вызывать sbrk только в том случае, если ни один из них не является достаточно большим.

person Giuseppe Guerrini    schedule 26.03.2011
comment
Спасибо, Джузеппе - значит, я уже сделал все, что вы сказали выше. Моя проблема связана с моей коллекцией бесплатных блоков: когда у меня есть свободный блок, я иногда хочу разделить его на 2 меньших блока. Я делаю это, просто изменяя свой metaStruct так, чтобы он говорил size = size / 2 или что-то в этом роде. Затем я получаю указатель на вторую половину моей памяти - вот где возникает моя проблема. Я использую указатель, как и вы, но когда я делаю m- ›size, происходит сбой. Есть идеи, почему? В очередной раз благодарим за помощь :)) - person Navin Aggrawal; 26.03.2011
comment
@Navin: почему ты хочешь разделить его пополам? Распределители обычно только разделяют куски в malloc (), возвращая пользователю один кусок запрошенного размера, а остальное оставляя как новый кусок в свободном списке. - person ninjalj; 26.03.2011
comment
@ninjalj: Я думаю, OP реализует распределитель системы приятелей, широко известный как худший тип ... - person R.. GitHub STOP HELPING ICE; 26.03.2011
comment
@Navin: есть много вещей, которые могут пойти не так, если вы выплюнете свободный блок. По крайней мере, вы должны проверить, достаточно ли велика оставшаяся часть, чтобы содержать заголовок плюс минимальный объем данных. Кроме того, в большинстве систем важно выравнивание указателя, поэтому вы должны убедиться, что вторая часть начинается (по крайней мере!) С кратного слова физического процессора (а этого может быть недостаточно). В зависимости от системы использование невыровненного указателя может вызвать исключения, непредвиденное поведение или потерю производительности. - person Giuseppe Guerrini; 26.03.2011
comment
@Navin (продолжение): типичный шаблон для безопасного разделения ploc: округлить размер, который вам нужен, до размера системного слова; если block- ›size-required_zie› sizeof (metaStruct), вы можете разделить; иначе сдаваться. Возможный способ разделения блока: newblock = (metaStruct *) (((char *) block) + sizeof (metaStruct) + rounded_size). - person Giuseppe Guerrini; 26.03.2011
comment
Привет, спасибо, Джузеппе, так что да, я разделяю свободный блок, потому что, когда я malloc, если я найду блок, который значительно больше, чем мне нужно, я хочу иметь возможность использовать только его часть, а остальное поместить в свой бесплатный список . Как узнать размер системного слова? Я думаю, что ваш совет, вероятно, подскажет мне решение, но я не совсем уверен, что делать дальше. Насколько я понимаю, мой указатель не выровнен, и это может вызывать мои проблемы? - person Navin Aggrawal; 27.03.2011
comment
Привет, Навин. Моя - всего лишь гипотеза, неверно выровненный указатель МОЖЕТ вызвать проблемы (например, на ARM). Правильное выравнивание существенно зависит от используемого вами процессора, поэтому необходимо изучить архитектуру процессора. Компилятор может добавлять некоторые правила, поэтому вам также следует обратить внимание на то, как компилятор все выравнивает. Вот статья, которая может быть для вас наполовину полезной: http://stackoverflow.com/questions/2505912/c-64-bit-pointer-alignment. Пока! - person Giuseppe Guerrini; 27.03.2011
comment
Спасибо, Джузеппе. Я удалил код, который выполняет расщепление, и, как мы и подозревали, мои ошибки исчезли! Итак, в основном мне нужно научиться правильно разбивать свободные блоки / с выровненными указателями. Любые советы о том, как это сделать, будут оценены - person Navin Aggrawal; 28.03.2011
comment
Предположим, что необходимое выравнивание для вашей системы - это a, b - указатель на блок для slpit, а s - требуемый размер. Размер можно округлить следующим образом: s = s + a - ((s-1)% a) +1. Указатель p на свободную часть блока равен p = (metaStruct *) (((char *) (& b [1])) + s). Я надеюсь, что эти простые заметки могут вам помочь. Пока! - person Giuseppe Guerrini; 29.03.2011