Как узнать структуру памяти вашей реализации структуры данных на компьютере с 64-разрядной версией Linux

В этой статье http://cacm.acm.org/magazines/2010/7/95061-youre-doing-it-wrong/fulltext

Автор рассказывает о макетах памяти из двух структур данных: "Бинарная куча" и "В-куча" и сравнивает, как лучше иметь макет памяти, чем другой (рисунки 5 и 6).

Я хочу получить опыт в этом. У меня есть реализация N-Ary Tree, и я хочу узнать структуру памяти моей структуры данных. Каков наилучший способ придумать макет памяти, такой как в статье?

Во-вторых, я думаю, что легче определить макет памяти, если это реализация на основе массива. Если в реализации дерева используются указатели, то какие инструменты у нас есть или какой подход требуется для сопоставления его макета памяти?

Ответ 1

Создайте код для data-structure для тестирования

Предварительно заполните тег data-structure со значительными значениями (0x00000000, 0x01111111,...), выделив границы макета и данные, принадлежащие элементам data-structure

Используйте инструменты отладки для просмотра актуального содержимого и макета живой памяти, которые кодированный data-structure элемент-под-тестом использует in-vivo

(быть систематическим и терпеливым)

Ответ 2

Возможно, просто перемещение структуры данных для печати адресов элементов (и размеров, если они меняются) даст вам достаточно информации для подачи, например, graphviz? Я не уверен, почему вы включили тег linux-kernel. Основное сопоставление виртуальной памяти происходит при детализации страницы (игнорируя здесь огромные страницы), поэтому физический виртуальный адрес не имеет значения. Вы можете легко выполнять свои тесты в пользовательском пространстве.

Я бы сделал следующее:

поместите вызовы для сброса ваших N-арных деревьев в код или используйте GDB script, чтобы сделать это
напишите script на вашем любимом языке сценариев, чтобы группировать объекты на страницы (маскировка более низких 12 бит адресов дает идентификатор страницы), вычислять статистику, просматривать объекты, охватывающие несколько страниц, делать все, что вы хотите; output graphviz файл описания
запустите graphviz, чтобы наслаждаться визуализацией.

Ответ 3

Первое, что вам нужно сделать, это выяснить данные, которые вам нужно представить в графическом формате. Макет памяти в рисунках Poul-Henning Kamp - это как структура указателя, так и смежные страницы виртуальной памяти. Первый может быть легко отображен с помощью инструмента отладки, такого как ddd. Последнее требует немного больше усилий, и есть еще много способов сделать это.

Несколько идей...

Напишите функцию для перемещения структуры данных и значений печати, скомпилируйте ее как код эстакады и запустите
Добавить функцию и вызвать ее из отладчика, например gdb
Напишите script для вызова из отладчика

Еще одна возможность, о которой никто еще не упоминал, будет читать спецификацию для языка, на котором вы пишете код. Это, как правило, позволяет определить макет памяти структур в самом компилированном коде (C/С++ и т.д.)...), пренебрегая оптимизацией компилятора. Это можно изменить, сообщив компилятору о том, чтобы выложить структуры данных не по умолчанию, хотя (alignas, __attribute__(aligned) и т.д.). Вам все равно нужно будет рассмотреть, как выделяется память из кучи и операционной системы.

Однако, как только у вас есть соответствующие значения, вы сможете использовать любое программное обеспечение, которое хотите преобразовать данные в графический формат (graphviz и т.д.).