|
Re^3: [OT] Stats problem
by roboticus (Chancellor) on Feb 27, 2015 at 00:26 UTC
|
BrowserUk:
For that particular use case, you might try something I did when I had a similar problem: Put a matching marker just *before* the address you return in your malloc routine. (In mine, I had a counter inside of malloc, so the marker just happened to be the number of times malloc was called (plus the starting value). I bracketed the requested memory area with the marker, and filled the block with junk. I added the 'before' marker because I was tracking down a buffer overrun as well. (Another thing I did was to put the caller's address and the requested allocation size in the preamble as a debugging aid. Fit nicely in a 'paragraph' in 32-bit mode.
...roboticus
When your only tool is a hammer, all problems look like your thumb.
| [reply] |
|
|
That would certainly be advantageous in that it would allow you to definitively detect which address the overrun had occurred through.
The downside is that it adds another 4 bytes to the overhead for every allocation. Probably not a problem for a debug malloc library -- although one of the problems I had was that when I enabled the debug malloc, the program which was designed to run close to the limits of my physical memory without going into swapping, moved into swapping and ran like it was swimming n molasses as a result. So much so that I had to modify the parameters to reduce the memory usage to 1/4 to avoid swapping; which in turn meant that the problem I was trying to track down never actually occured.
The real advantage of the method I described is that it uses no extra space in actual allocation as it is only written to free space slots. Either when the virtual memory is first obtained; or when a pointer is freed. Of course, it will then only detect overruns if the happen to encounter a free slot; but with the advantage that they can remain enabled, at very little overhead, in production code.
I also had the notion of using two interleaving, free space chains. The first would be used, leaving (at least one) free space between all allocations, until it filled. Only then would the second be used. That might afford early(er) and more accurate detection of overruns.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
| [reply] |
|
|
BrowserUk:
Yeah, it can consume more memory. I always had a paragraph at the beginning, but the marker at the end was "free" roughly 1/4 of the time, since the allocator had to round up to the next paragraph anyway (MSVC 6.0, I don't know if it has the same strategy/constraints in newer versions).
I really like the idea of two interleaved free chains to aid in detection. I noticed that in the applications I worked on, that allocation usually happened in just a few particular sizes, so allocating two blocks at a time (both of the same size) and dropping the second one into a free list might be interesting. I'll have to remember this when I do my next fun C/++ job.
...roboticus
When your only tool is a hammer, all problems look like your thumb.
| [reply] |
Re^3: [OT] Stats problem
by SuicideJunkie (Vicar) on Feb 26, 2015 at 20:30 UTC
|
If you don't mind the debug mode speed hit, you could use an alternate memcpy() and friends.
The idea being, the memory functions will check the values they're copying, and assert that they're not writing the telltale value, since it should never be used as a value in your program.
| [reply] |
|
|
| [reply] |
Re^3: [OT] Stats problem
by salva (Canon) on Feb 27, 2015 at 10:09 UTC
|
mem[ix] = ix ^ magic_value;
| [reply]
[d/l] |
|
|
| [reply] |
|
|
Because an offset/ptr follows a too simple pattern and potentially there could exist specific bugs patterns where the overwriting data and the marker match.
The xor-with-a-constant operation has the interesting property of keeping the variability, it would just made the ptr values not look like ptrs.
In other words if for instance you have an array a with 10 elements, the probability of your code generating the value a+10 is higher than (a+10)^0xdeadbee5.
| [reply]
[d/l]
[select] |
|
|
Re^3: [OT] Stats problem
by QM (Parson) on Feb 27, 2015 at 11:40 UTC
|
As the 4GB offset repeats periodically, why not some unpredictable, non-periodic function that can be easily created and checked?
- random value based on 64 bit address as seed (last 32 bits)
- MD5 hash (last 32 bits)
- XOR of upper and lower 32 bits of address
I'm sure you can come up with better, faster functions.
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply] |
|
|
non-periodic function that can be easily created and checked?
Any time you squeeze a 64-bit value (address) into a 32-bit pot, you are going to get repeats.
The good thing with using the offset directly is that you know that the repeats are always going to be 4 billion bytes apart. And thus only occur if the program uses more than 4GB of heap; and on my 8GB only occur twice. (Not strictly true if I allowed my machine to go into swapping!)
With any non-periodic function, the repeats will (must) still occur, the only difference is that the spacing will vary, and be less. It could even put then in adjacent memory slots; or certainly a lot closer together.
Intuitively -- though as I observed elsewhere, there is nothing much that is intuitive about this -- the danger of the copy-over problem seems more likely the closer together they are.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
| [reply] |
|
|
Yes, yes, all valid points. I was just trying to remove one more weakness, which is the 4GB offsets matching.
Consider that anything that hits the 4GB+x weakness will be undetectable, regardless of the length of the overrun. (OK, within reason, as a long enough overrun will surely break something else.)
Under an MD5 hash scheme, the chances of a 32bit slot being overwritten with the correct magic data is 1/4G, the same as with the offset method. But for the offset method, if the from/to addresses are 4GB apart, a run will generate the correct data, regardless of the length of run. For MD5 hash, the probabilities are independent, even for a malloc overrun as in the example, because consecutive hash values are not dependent on the neighboring hash values in any simple way.
Still, 1/4G is quite small.
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply] |