[C++] Ideeën over een oplossing voor synchronisation

[evolution536]

Beste medetweakers,

Ik ben al een aardige tijd bezig met een memory scanning applicatie. De functionaliteit houdt in dat er kan worden gescand naar bijv. 4-byte waarden in de readable memory pages van een proces. Deze memory pages worden opgehaald met VirtualQueryEx. Uit een scan komen een bepaald aantal resultaten. Dit kan verschillen tot een aantal honderdduizend tot miljoenen. Met deze resultaten kun je een nieuwe scan doen, op hetzelfde type primitief waarmee de huidige resultaten worden doorlopen en op die adressen opnieuw een compare wordt uitgevoerd. De opnieuw ingevoerde waarde wordt dan vergeleken met de oude en alle niet-kloppende resultaten worden verwijderd. Dit proces kan worden doorlopen totdat er 0 resultaten over zijn )

Nu heb ik echter een vervelend probleem, waarvan ik weet wat de oorzaak is. Ik heb echter nog geen werkende methode gevonden om het op te lossen. Het zit zo: De resultaten van een scan worden opgeslagen in een file. De file is effectief gewoon een array van memory adresses (unsigned int*). Na een scan sla ik in het geheugen op welke index de resultaten bevat van welke memory page, aangezien ik dit moet weten, zou ik een volgende scan willen uitvoeren die net zo snel draait als de eerste scan.

De scans worden zo efficient mogelijk (probeer ik) geparalleliseerd, aangezien dit de scan met een noodgang versnelt. In mijn geval, i7 2600k, worden er 8 threads gestart door een threadpool die het werk afhandelen. Iedere thread krijgt een deel van de memory pages die zijn gevonden door VirtualQueryEx en alle resultaten die de thread vindt worden opgeslagen in een thread-local array. Wanneer de thread klaar is kan dit array zo in de file worden geschoven, erg gemakkelijk vind ik!

De threads worden tegelijk gestart, maar de ene thread is eerder klaar dan de ander, in wat voor volgorde dan ook. Dat betekent dat de volgorde van de file niet thread 1,2,3,4,5,6,7,8 is, maar bijna altijd een random volgorde. Hier begint mijn probleem. Ik vind het niet belangrijk dat de resultaten niet zijn gesorteerd, aangezien de UI een cache gebruikt in het RAM die los van de file wordt beheerd. Het probleem is: hoe krijg ik bij een volgende scan de resultaten in de juiste thread? Een volgende scan wordt ook geparalleliseerd over 8 threads, wat betekent dat iedere thread precies de juiste set van memory pages toegewezen moet krijgen, anders zullen de ingeladen waarden van de file niet kloppen. Hier gaat het op fout. De volgende code ter verduidelijking:

C++:

const unsigned int currentResultPtr = AddressesFileMapping->Get(resultIndex);
const unsigned int bufferOffset = (lastRegionAddress - currentResultPtr);
const T* currentDataPtr = (T*)(buffer + bufferOffset);

AddressFileMapping is de interface die de file als T[] aanbiedt. In dit geval: T = unsigned int (memory addresses). resultIndex moet hier dus altijd tussen de startindex en de eindindex van de memory page zitten, anders klopt de rest van de berekening niet, lijkt me. De berekening is als volgt bedacht:

lastRegionAddress = laatste memory address van de huidige memory page (iteratie door de toegewezen memory pages aan deze thread)
bufferOffset = lastRegionOffset - currentResultPtr. Dit zou dus de offset moeten zijn relatief gezien vanaf het base address van de memory page
currentDataPtr = de buffer pointer + de offset. De buffer is de lokaal ingelezen memory page, met precies dezelfde lengte als de memory page. Logisch gezien zou dus buffer + offset uit moeten komen op dezelfde positie in de memory page, maar dan relatief ten opzichte van mijn lokale buffer! Correct right?

Hier gaat het constant fout. Ik wil het liefst de indexes en lengths van welke memory page zijn resultaten waar in de file heeft staan in het RAM houden aangezien dit mijn code een heel stuk gemakkelijker maakt en ook het beheren van de file zeer veel gemakkelijker maak. Mijn vraag is in feite: Hoe zou ik dit efficient kunnen doen? Ik kamp nogal met dit probleem, als dit proces dynamisch werkt is mijn probleem heel ver verholpen. Nog een keer: gesorteerde resultaten vind ik niet belangrijk! Aangezien ik hier waarschijnlijk threads moet gaan blokkeren wordt de scan hier alleen maar langzamer op

Alvast bedankt!

[Juup]

Je verhaal is nogal lang en warrig.
Het feit dat je het probleem niet in een paar woorden kan uitleggen betekent waarschijnlijk dat je het probleem zelf nog niet goed begrijpt.

Analyseer je probleem dieper.

Ook zie ik je vaak bevestiging zoeken voor designkeuzes die je niet los wilt laten. Dit houdt je "in the box" en misschien is dit probleem niet binnen je box oplosbaar.

[MSalters]

Inderdaad. Je design is fundamenteel fout: de tweede scan heeft niet noodzakelijkerwijs dezelfde pages als de eerste. Los dat eerst op, en je ziet dat een fatsoenlijke oplossing verderop een stuk makkelijker wordt.

Ik zou overigens de scan-procedure compleet scheiden van de vergelijkingsprocedure. Je wil tenslotte de scan 2 keer runnen en de vergelijking dan 1 keer.

[Mijzelf]

Ik betwijfel of parallelliseren hier überhaupt iets oplevert. Tenzij je vergelijk routine erg inefficiënt is, lijkt me de geheugenbandbreedte de beperkende factor, niet de processorkracht.

[PrisonerOfPain]

Je moet je resultaten niet in je TLS opslaan maar in een aparte (globale) lijst, de waarnaar je schrijft kun je het makkelijkste bijhouden met een atomic - zolang je iedere keer een even grote dataset oplaat.

Mijzelf schreef op woensdag 03 juli 2013 @ 13:26:
Ik betwijfel of parallelliseren hier überhaupt iets oplevert. Tenzij je vergelijk routine erg inefficiënt is, lijkt me de geheugenbandbreedte de beperkende factor, niet de processorkracht.

Je houd geen rekening met je caches.

[evolution536]

Het is behoorlijk out of the question om de data in het RAM op te slaan. In het begin heb ik dit gedaan, maar hier krijg je ontzettend snel out-of-memory situaties, omdat het hier soms om tussen de 30 en 150 miljoen resultaten gaat. Neem aan dat we het over een 4-byte integer hebben, dan komt het al neer op honderden megabytes, waar ik met grotere datatypen al snel over de 1,5 GB memory usage heen ging.

Ook moet ik dit wel parallelliseren aangezien met 1 thread dit een aantal minuten duurt waar het met 8 threads met 2-3 seconden klaar is. Overigens is het in dit geval wel zo dat de tweede scan dezelfde memory pages omvat. Voor de duidelijkheid: een tweede scan is om de eerdere resultaten te herzien en de addressen van deze resultaten opnieuw te vergelijken met een opgegeven waarde. De adressen staan vast, dus de pages worden hier gebruikt om sneller grotere blokken geheugen per ReadProcessMemory call in te lezen.

Ik ben nog bezig met het zoeken naar een oplossing. Ik heb mijn verhaal niet erg duidelijk kunnen omschrijven, helaas. Mijn excuses daarvoor. Ik probeer in feite mijn eigen software te maken die hetzelfde doet als Cheat Engine. Misschien helpt dit

[PrisonerOfPain]

evolution536 schreef op woensdag 03 juli 2013 @ 16:14:
Het is behoorlijk out of the question om de data in het RAM op te slaan.

Je slaat het nu in je thread-local store op, dat staat ook gewoon in RAM.

[pedorus]

evolution536 schreef op woensdag 03 juli 2013 @ 16:14:
Ik probeer in feite mijn eigen software te maken die hetzelfde doet als Cheat Engine. Misschien helpt dit

Ik snap niet wat nu precies het probleem is; desnoods maak je gewoon een file per thread. Maar anders kun je ook eens in de source van cheat-engine kijken, http://code.google.com/p/...trunk/DBKKernel/memscan.c

[MSalters]

evolution536 schreef op woensdag 03 juli 2013 @ 16:14:
Het is behoorlijk out of the question om de data in het RAM op te slaan. In het begin heb ik dit gedaan, maar hier krijg je ontzettend snel out-of-memory situaties, omdat het hier soms om tussen de 30 en 150 miljoen resultaten gaat. Neem aan dat we het over een 4-byte integer hebben, dan komt het al neer op honderden megabytes, waar ik met grotere datatypen al snel over de 1,5 GB memory usage heen ging.

Foute methode. Gebruik een bitmap met 500 miljoen bits, want je target proces heeft maximaal 500 miljoen integers. Die 500 miljoen bits zijn samen maar 64 MB.