Forum: PC-Programmierung [c] Suche Allocator, bei dem man den Anfang eines reservierten Bereichs ermitteln kann


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Daniel A. (daniel-a)


Angehängte Dateien:

Lesenswert?

Hallo Zusammen

Bei einem meiner Projekte habe ich sehr viele string Datentypen mit 
diversen Memory Managemant Anforderungen, und es läuft langsam aus dem 
Ruder. Ich habe normale Strings, readonly Strings, Strings mit Referenz 
Counter, solche mit Hashes, welche mit einem eindeutigen Pointer aus 
einem Hash-set, und Kombinationen davon, sowie Sachen die zwischen 
manchen konvertieren.

Jetzt will ich zumindest mal das Memory Managemant vereinfachen, und das 
Reference Counting in einen eigenen Allocator verschieben. Ich habe dann 
Funktionen, die je nachdem die Strings kopieren, oder Referenden 
Counting machen, abhängig davon, woher die Dinger kommen. Wird also dann 
relativ Transparent gehandhabt werden, und ich kann dann viele 
Schnittstellen viel Toleranter gestalten, was für Daten sie annehmen.

In example.c im Anhang sieht man, wie ich mir das gedacht habe.

Mein Hauptproblem ist nun, ich möchte solche Sachen machen können:
1
char* hello = dpa_dup("Hello Sunny World!", 19);
2
dpa_ref(hello + 6); // rc 1->2 
3
dpa_ref(hello);     // rc 2->1
4
dpa_put(hello + 6); // rc 2->0, "Hello Sunny World!" wird freigegeben

Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der 
Allokation "hello" ist. Ich muss irgendwie an die selben Metadaten 
kommen. Ob der Allokator eine Funktion dafür hat, oder eine um den 
Anfang der Allokation zu ermitteln, ist egal, ich brauche einfach was, 
um da nachher ran zu kommen.

Ansonsten habe ich den Rest der API schon mal vorbereitet (siehe 
Anhang). Ich brauche nur noch einen Allocator, der die Funktionen 
dpa_mem_impl_realloc und dpa_mem_impl_find_allocation_start 
implementiert, und dem ich meine Funktionen dpa_internal_allocate_pages 
und dpa_internal_free_pages mitgeben kann (die sind wrapper um mmap 
herum, die aus einem 1TB grossen, per mmap PROT_NONE reservierten 
Bereich, pages neu mappen und zurück geben).

Einen Allocator zu finden, der ein realloc bereitstellt, ist ja kein 
Problem. Das Problem ist einen zu finden, mit dem ich 
dpa_mem_impl_find_allocation_start umsetzen kann. Oder halt sonst wo 
meine Metadaten ablegen kann.

Selber schreiben würde ich den Allocator eher ungern. Das richtig und 
effizient hin zu kriegen ist schwierig.

von MaWin O. (mawin_original)


Lesenswert?

Daniel A. schrieb:
> Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der
> Allokation "hello" ist.

Sehr ungewöhnlich.
Warum brauchst du das?

von Nikolaus S. (Firma: Golden Delicious Computers) (hns)


Lesenswert?

MaWin O. schrieb:
> Daniel A. schrieb:
>> Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der
>> Allokation "hello" ist.
>
> Sehr ungewöhnlich.
> Warum brauchst du das?

Finde ich auch ungewöhnlich. Normalerweise behält man eine (weitere) 
Referenz auf hello+0 um den gesamten Speicher freigeben zu können. Denn 
es ist m.E. nicht mal offensichtlich ob mit dpa_put(hello + 6) der 
Speicher von hello+0 bis hello+5 gekürzt oder auch mit freigegeben 
werden soll. Das kann man mit free(hello) oder realloc(hello, 6) 
steuern.

: Bearbeitet durch User
von Niklas G. (erlkoenig) Benutzerseite


Lesenswert?

Daniel A. schrieb:
> normale Strings

std::string

> readonly Strings

const std::string

> Strings mit Referenz Counter

std::shared_ptr<std::string>

duck und wech...

von Daniel A. (daniel-a)


Lesenswert?

Nikolaus S. schrieb:
> MaWin O. schrieb:
>> Daniel A. schrieb:
>>> Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der
>>> Allokation "hello" ist.
>>
>> Sehr ungewöhnlich.
>> Warum brauchst du das?
>
> Finde ich auch ungewöhnlich. Normalerweise behält man eine (weitere)
> Referenz auf hello+0 um den gesamten Speicher freigeben zu können. Denn
> es ist m.E. nicht mal offensichtlich ob mit dpa_put(hello + 6) der
> Speicher von hello+0 bis hello+5 gekürzt oder auch mit freigegeben
> werden soll. Das kann man mit free(hello) oder realloc(hello, 6)
> steuern.

Wenn ich eine Funktion habe, ich übergebe ihr einen Member eines 
Structs, und etwas anderes braucht das später noch, dann muss ich eine 
design Entscheidung auf API Ebene treffen. Halte ich eine Referenz auf 
das darüberliegende Struct irgendwo vor? Muss / kann ich es kopieren? 
Soll die Funktion davon wissen, oder lasse ich den Caller das regeln? 
etc.

Wenn ich wenn möglich refcounting direkt im Allokator mache, wird die 
Situation simpler und Homogener. Der Allokator muss ja sowieso wissen, 
wie Gross der Speicherbereich ist, auf den ein Pointer zeigt, um ihn 
freizugeben. Er müsste die Referenz also schon in gewisser Weise haben.
Damit muss man nun auf API Ebene keine design Entscheidung mehr treffen, 
ob man diese behält, oder nicht, usw. Das Problem wird reduziert auf die 
Frage, ob und wo man die Daten kopiert. Eine Änderung in der 
Implementation, aber nicht an der API oder den Datenstrukturen. Ich 
kopiere sie nicht -> Äquivalent zum Behalten einer Referenz auf den 
Block. Ich kopiere sie in der Funktion -> nur ein zusätzlicher 
Funktionsaufruf dort. Ich kopiere sie vor dem Funktionsaufruf -> auch 
nur ein Funktionsaufruf dort.

Ausserdem unterteile ich den Speicher per Adresse in 3 Teile: Nicht von 
mir angelegt, Mir Refcounting rw, ohne Refcounting readonly (selber 
speicher nochmal gemappt mit anderen Zugriffsrechten). Wenn ich die 
readonly Adressbereiche so nutze, dass ich sie nicht nur als nur Lesbar, 
sondern als Unveränderbar behandle, kann ich noch weitere Optimierungen 
machen. Ich weiss nicht nur, wann ich meine Daten nicht ändern werde, 
sondern, dass niemand das tut. Und damit kann ich dann bei const 
Parametern weitere Optimierungen machen, nämlich, unveränderbaren 
Speicher nicht zu kopieren. Darum muss ich mich dann also auch nicht 
mehr selbst kümmern. Ein paar unnötige Kopien wird es trotzdem geben, 
ich habe noch keinen Check eingebaut, wo die .rodata der Anwendung hin 
gemappt wurden, das wäre noch optimierungsfähig. Dennoch, recht nun auch 
hier eine einzige API um alles abzudecken.

Niklas G. schrieb:
>> readonly Strings
>
> const std::string

Wie oben beschreiben, ich mache da teils etwas härtere, nur zur runtime 
relevante, Designentscheidungen, als const alleine sicherstellen könnte.

von Niklas G. (erlkoenig) Benutzerseite


Lesenswert?

Daniel A. schrieb:
> Damit muss man nun auf API Ebene keine design Entscheidung mehr treffen,
> ob man diese behält, oder nicht, usw.

Also in C++ macht man es genau so. Der Parametertyp einer Funktion gibt 
an, ob kopiert wird oder nicht, oder die Funktion "owner" wird, ob 
Referenzzählung gemacht wird. Das dynamisch zur Laufzeit zu 
unterscheiden erschwert die Fehlersuche und ist ineffizient.

Daniel A. schrieb:
> Ich weiss nicht nur, wann ich meine Daten nicht ändern werde,
> sondern, dass niemand das tut. Und damit kann ich dann bei const
> Parametern weitere Optimierungen machen, nämlich, unveränderbaren
> Speicher nicht zu kopieren.

Klingt verdreht; eine Funktion/API welche Daten zum Auslesen bekommt, 
kopiert den Speicher eigentlich nie, sondern nimmt an, dass er konstant 
bleibt. Der Aufrufer muss dafür sorgen dass nichts geändert wird und 
ggf. die Kopie machen. Auch das braucht nicht zur Laufzeit entschieden 
werden.

von MaWin O. (mawin_original)


Lesenswert?

Das liest sich unnötig komplex und wie die Neuerfindung des Rades.
Warum kein Standard-Malloc oder Stdlib-Primitive?

von Daniel A. (daniel-a)


Lesenswert?

1
void f(const int* b);
2
int a;
3
f(&a);

Meistens weiss eine Funktion, wann sich der Wert einer Variable 
verändern kann. Aber sobald dass nicht mehr der fall ist, und/oder eine 
Unterfunktion das Objekt für länger behält, muss man es eventuell schon 
rein vorsichtshalber mal kopieren. Auch wenn das gar nicht nötig wäre. 
Ein X* lässt sich halt in ein const X* Konvertieren. Woher kam das 
Objekt noch gleich, lebt es lang genung, etc.? Klar, man kann immer mehr 
und strengere Typen drauf werfen, um das zu beschreiben. Und APIs darauf 
beigen, für die diversen Fälle.

Aber ich bin an einem Punkt angekommen, wo ich viele Typen habe, viele 
Semantiken unterstützen will, und das ganze unübersichtlich wird. Darum 
streiche ich das ganze und Wechsel einer simpleren, universelleren API.

von Niklas G. (erlkoenig) Benutzerseite


Lesenswert?

Daniel A. schrieb:
> Aber sobald dass nicht mehr der fall ist, und/oder eine
> Unterfunktion das Objekt für länger behält, muss man es eventuell schon
> rein vorsichtshalber mal kopieren.

Klingt nach einem Design-Fehler. Solche Probleme hab ich auch bei stark 
asynchroner Programmierung noch nicht gesehen. Unnötiges Kopieren ist 
sowieso ineffizent, das vermeidet man soweit wie möglich.

Daniel A. schrieb:
> Woher kam das
> Objekt noch gleich, lebt es lang genung, etc.?

Bei vernünftiger Architektur ist das alles klar ersichtlich. Durch 
Verwendung der richtigen Typen (std::string, const std::string&, 
std::string_view, std::shared_ptr<std::string>, 
std::unique_ptr<std::string>...) dokumentiert sich der Code selbst, und 
es ist genau zu ersehen wo Objekte erstellt, "owned", referenziert, 
gelöscht werden.

Das ist doch gerade der Sinn von nativen Sprachen wie C und C++, dass 
man den Speicher explizit selbst verwaltet. Wenn man das nicht will, 
kann man auch Java nutzen. Da gibt es für alles den "String"-Typ, der 
ist immer read-only und muss zum Modifizieren kopiert werden, ist somit 
auch bei echten Konstanten effizient, Garbage Collection inklusive.

: Bearbeitet durch User
von Daniel A. (daniel-a)


Lesenswert?

Ich habe es mit einer Library zutun. Mit dynamischen Baumstrukturen, 
eine art DOM. Dazu noch diverse Parser und Serializer. Und wenn es nicht 
nötig ist, komme ich tatsächlich ohne Kopieren aus. Aber ich habe 
Situationen, wo sich nur der Besitzer von Speicher ändert, und solche, 
wo der Speicher nicht statisch ist, und ich ihn kopieren muss, und ein 
paar andere Fälle. Und die APIs decken das auch alles ab. Aber Simpel 
ist das Design nicht mehr, und das gefällt mir nicht. Wie schon gesagt, 
ich habe mittlerweile nur schon mindestens ~5 String Typen. Und 
Situationen, wo ich einen hashed String brauche, aber einen refcounted 
string habe, oder umgekehrt, oder auch mal einen hashed refcounted 
string (oder war es refcounted hashed, ich weiss nicht mehr...), sind 
lästig, wenn ich da mal rein laufe, und dann auch mal was um designe...

Ich will ehrlich gesagt auch nicht wirklich darüber diskutieren, ob ihr 
meinen Ansatz toll findet oder nicht. Ich will einen neuen Ansatz 
ausprobieren, und dafür Fehlt mir nur noch diese eine kleine Sache, der 
Allocator. Bitte helft mir damit weiter.

von Foobar (asdfasd)


Lesenswert?

Da deine Strings anscheinen zu C-Strings kompatibel sein sollen, kannst 
du eh nur Unterreferenzen auf Endbereiche des Originalstrings erstellen 
- echte Substrings (von-bis) gehen nicht, da denen die \0 fehlen würde. 
Du könntest also die Verwaltungsinformationen (ref-counts etc) hinter 
den String packen - dort sind sie per p+strlen(p) jederzeit zu finden.

Allzu sinnvoll finde ich das aber nicht - ein eigenständiger String-Typ 
wäre deutlich flexibler.

von Daniel A. (daniel-a)


Lesenswert?

Wie schon gesagt, ich habe viele String typen. Wenn du in example.c im 
ersten Beitrag schaust 
(https://www.mikrocontroller.net/attachment/highlight/595363), dort habe 
ich ein struct für die Strings mit länge, pointer, (der auch nicht 
unbedingt null terminiert sein muss). Das sind aber auch nur Beispiele, 
ich könnte das an vielen Orten verwenden.

von Foobar (asdfasd)


Lesenswert?

Niklas schrieb:
> [Java] Da gibt es für alles den "String"-Typ, der ist immer read-only
> und muss zum Modifizieren kopiert werden, ist somit auch bei echten
> Konstanten effizient, Garbage Collection inklusive.

Lua macht das auch so.  Zusätzlich werden Strings "interned", d.h. 
Kopien vereinheitlicht.  Ist zwar beim Erzeugen einmalig etwas mehr 
Arbeit, danach sind String-Vergleiche aber nur noch Pointer-Vergleiche. 
Da bei Lua Variablen- und Feldnamen auch reguläre Strings sind, ist das 
ein wichtiges Kriterium.  Dass dabei auch noch Speicher gespart wird, 
ist ein positiver Nebeneffekt.

von Herbert B. (Gast)


Lesenswert?

Daniel A. schrieb:

Anstatt selber einen Garbagecollector zu bauen nimm doch gleich Java.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.