Zeiger, Verweiserkennung

Apollon

Hallo.

Sind Zeiger immer gleich gross und immer gleich Wortgroesse und werden demnach immer an 4 Byte Grenze ausgerichtet?

Die Frage ruehrt daher, dass ich einen Garbagecollector schreibe und dafuer Verweiserkennung betreiben muss. Die Frage ist nun wie ich das am besten bewerkstellige. Mir stehen vier char-Zeiger zur Verfuegung. Datensegmentanfang sowie Datensegmentende und Heapanfang sowie Heapende.

Wenn Verweise nun immer gleich Wortgroesse sind, dann kann ich den Datensegment mit einem int* durchiterieren ohne was zu verpassen. Falls nicht, wie erkenne ich einen Zeiger?

Danke.

c.rackwitz

> Sind Zeiger immer gleich gross
innerhalb einer architektur ja.
auf nem ueblichen 64 bit system ist ein pointer aber 8 byte gross und nicht 4 byte, wie auf einem uebrlichen 32 bit system.

> und immer gleich Wortgroesse
ich vermute mal schon.

> und werden demnach immer an 4 Byte Grenze ausgerichtet?
in welcher beziehung? sowas solltest du dem compiler ueberlassen und nur bei bedarf handoptimieren.

> Die Frage ruehrt daher, dass ich einen Garbagecollector schreibe und dafuer Verweiserkennung betreiben muss.
hm... malloc(), realloc(), free(), calloc(), strdup(),... ersetzen, atexit() fuers aufraeumen missbrauchen...

> Die Frage ist nun wie ich das am besten bewerkstellige.
s.o.

> Mir stehen vier char-Zeiger zur Verfuegung. Datensegmentanfang sowie Datensegmentende und Heapanfang sowie Heapende.
c kennt sowas nicht. redest du von assembly?

> Wenn Verweise nun immer gleich Wortgroesse sind, dann kann ich den Datensegment mit einem int* durchiterieren ohne was zu verpassen. Falls nicht, wie erkenne ich einen Zeiger?
sorry, das kann ich in keiner verbindung zu c sehen.
pointer inkrementieren bedeutet um die breite des bezeigten typen erhoehen. also "ja".
"zeiger erkennen" verstehe ich nicht.

Apollon

c.rackwitz schrieb:

> Sind Zeiger immer gleich gross
innerhalb einer architektur ja.
auf nem ueblichen 64 bit system ist ein pointer aber 8 byte gross und nicht 4 byte, wie auf einem uebrlichen 32 bit system.

> und immer gleich Wortgroesse
ich vermute mal schon.

> und werden demnach immer an 4 Byte Grenze ausgerichtet?
in welcher beziehung? sowas solltest du dem compiler ueberlassen und nur bei bedarf handoptimieren.

Ich meinte natuerlich an mod Wortgroesse Grenzen ausgerichtet. Sprich, dass ein Zeiger immer an einer durch Wortgroesse teilbaren Adresse liegen.

c.rackwitz schrieb:

> Die Frage ruehrt daher, dass ich einen Garbagecollector schreibe und dafuer Verweiserkennung betreiben muss.
hm... malloc(), realloc(), free(), calloc(), strdup(),... ersetzen, atexit() fuers aufraeumen missbrauchen...

Es ist kein echter Garbagecollector. Das ganze wird mehr oder weniger simuliert. Im Grunde muss ich nur zu malloc() aequivalente Funktion schreiben, die angeforderten Speicher bereistellt. Falls kein freier Speicher mehr vorhanden ist, fuehrt sie Bereinigung durch, indem sie nicht gebrauchte Bereiche wieder als frei markiert und somit zur weiteren Verwendung freigibt.

c.rackwitz schrieb:

> Mir stehen vier char-Zeiger zur Verfuegung. Datensegmentanfang sowie Datensegmentende und Heapanfang sowie Heapende.
c kennt sowas nicht. redest du von assembly?

Nein. Hiervon:

struct memory_info {
  char* heap_start;    /* Anfangs- und */
  char* heap_end;      /* Endadresse der Halde */
  char* data_start;    /* Anfangs- und */
  char* data_end;      /* Endadresse des globalen Datenbereiches */
};

extern void get_memory_info(struct memory_info* info);

c.rackwitz schrieb:

> Wenn Verweise nun immer gleich Wortgroesse sind, dann kann ich den Datensegment mit einem int* durchiterieren ohne was zu verpassen. Falls nicht, wie erkenne ich einen Zeiger?
sorry, das kann ich in keiner verbindung zu c sehen.
pointer inkrementieren bedeutet um die breite des bezeigten typen erhoehen. also "ja".
"zeiger erkennen" verstehe ich nicht.

Mein Ansatz waere so:

unsigned int* iterator = (int*)mem_info->data_start;
if (iterator >= mem_info->heap_start && iterator <= heap_end) {
    moeglicherweise ein zeiger auf benutzten speicherbereich.
    speicherbereich auf den iterator zeigt als benutzt markieren,
    uebrpruefen ob im speicherbereich auch ein verweis liegt und prozedur wiederholen
}
das ganze fuer iterator++ bis iterator == mem_info->data_end

An dieser Stelle ist es relevant, ob Verweise immer durch Wortgroesse teilbar sind und entsprechend ausgerichtet sind, denn falls nicht, dann uebersehe ich meoglicherweise welche.

c.rackwitz

ich verstehe immer noch nicht, was du mit verweisen meinst und was dich ueberhaupt das alignment kuemmert.
was iterierst du ueber speicher? damit kriegst du keine infos von irgendwas.

malloc() ist ganz anders implementiert, wie du das vll im sinn hast.
malloc() hat mehrere pools von verschiedenen blockgroessen, aus denen speicher genommen wird und dabei wird aus dem pool (verkettete liste) diese stueck entfernt. wird es wieder freigegeben, dann kommt in die poolliste wieder ein record, welches den speicher als frei markiert. (irgendwann zieht der pool ziemlich fragmentiert aus und malloc() vereint angrenzende freie bloecke.)

Apollon

Ok. Das war etwas missverstaendlich. Ich versuche es mal anders.

struct NODE {
    int val;
    NODE* next;
};

struct NODE* newNode()
{
    struct NODE* n1 = gcmalloc(sizeof(struct NODE)); /* dieser speicherbreich wird nicht freigegeben und auch nicht mehr erreichbar => kann entsorgt werden da auf ihn kein verweis nach ende von newNode() existiert */
    struct NODE* n2 = gcmalloc(sizeof(struct NODE)); /* dieser wird zurueck gegeben und wird verwendet */
    return n2;
}

int main()
{
    struct NODE* list = newNode(); /* <= das ist ein gueltiger verweis auf einen speicherbereich im heap. den muss ich erkennen. liegt im datenbereich */
    list->next = newNode(); /* dieser verweis liegt im heap. ihn muss ich auch erkennen und falls er gueltig ist, den speicherbereich auf den er zeigt als benutzt markieren */
    /* hier ganz viel sehr komplizierter code welcher newNode() sehr oft verwendet */
    return 0;
}

Ich hoffe das war jetzt etwas klarer. Und wenn nicht, auch egal. Du hast mir bereits weitergeholfen. Danke.

c.rackwitz

du willst reference counts. in ansi c hast du aber so eine art destruktor nicht (mit dem man die gut wieder dekrementieren koennte), weshalb es imho unmoeglich ist, ein automatisches verwerfen oder "out-of-extent" (pointer stirbt, bezeigtes willst du free()n) automatisch zu erkennen. du kannst hoechstens atexit() wieder alles free()n oder auf ein vom user benutztes gcfree() reagieren, aber sonst ist sense.

du kannst nicht irgendwie nach validen pointern rumscannen, geht nicht. leider.
du koenntest aber in der sprachreferenz (letzter draft, so gut wie die bezahlvariante) [1] des ISO/IEC JTC1/SC22/WG14 [2] nach sachen suchen, bei denen du anhebeln kannst.

sag bitte statt "verweis" einfach pointer, zeiger oder referenz.

noch ein paar links wahllos zusammengegoogelt: [3] [4] [5]
GC ist also doch in C moeglich, aber die sprache selbst ermoeglicht es nicht, sondern nur hacks der sprache (heap nach dingen scannen, die wie pointer aussehen...)

[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf
[2] http://www.open-std.org/jtc1/sc22/wg14/
[3] http://www.hpl.hp.com/personal/Hans_Boehm/gc/
[4] http://www.utdallas.edu/~ramakrishnan/Projects/GC_for_C/
[5] http://www.iecc.com/gclist/GC-faq.html

supertux

atexit ist wirklich eine interessante Funktion.

Wie sicher ist es mit dieser Funktion zu arbeiten? Ich hab die Man Page gelesen und da gibt es ein Beispiel, da kommt nämlich sowas vor:

i = atexit(bye);
if (i != 0) {
       fprintf(stderr, "cannot set exit function\n");
       return EXIT_FAILURE;
}

was für welche Gründe kann es geben, dass atexit != 0 zurückgibt? Denn wenn ich sicher bin, dass diese Funktion nie != 0 zurückgibt, kann ich für ein eigenes Projekt eine kleine GC schreiben.

c.rackwitz

http://www.openbsd.org/cgi-bin/man.cgi?query=atexit&apropos=0&sektion=0&manpath=OpenBSD+Current&arch=i386&format=html

ERRORS
[ENOMEM] No memory was available to add the function to the list.
The existing list of functions is unmodified.

supertux

c.rackwitz schrieb:

http://www.openbsd.org/cgi-bin/man.cgi?query=atexit&apropos=0&sektion=0&manpath=OpenBSD+Current&arch=i386&format=html

ERRORS
[ENOMEM] No memory was available to add the function to the list.
The existing list of functions is unmodified.

hmm... meine man page hat genau das nicht

ich frage mich, wie oft es vorkommt, dass atexit keinen Speicher findet, um die Funktion in die Liste hinzuzufügen.

c.rackwitz

int main(void) { for(;;) malloc(1<<15); return 0; }

...im hintergrund und dann...

void foo(void) {} int main(void) { for(;;) atexit(&foo); return 0; }