4 ms·
The idea of redefining pointers from an {address} to an {offset,allocation_id} tuple seems to me a very powerful solution to the problems discussed recently in
by bumholio 8y ago
The idea of redefining pointers from an {address} to an {offset,allocation_id} tuple seems to me a very powerful solution to the problems discussed recently in "C's biggest mistake: conflating pointers with arrays" [1]
Instead of redefining arrays and introduce a new incompatible syntax, we are redefining the compiler representation of what a pointer is and get run-time guarantees of correctness without modifying the source code of existing C and C++ programs. For example, on a 64 bit machine a pointer can become an 128 bit long concatenation of two address:
[ptr][alloc_id]
The [ptr] part is binary equivalent of existing C pointers (the memory address of the pointed object), while the alloc_id is another 64 bit address of the allocation structure from which the object is part of. Here is a "fat" pointer that indexes the 4th element of an array, previously allocated by malloc(8 * sizeof(object)) :
[ ][ ][ ][ ][ ][ ][ ][ ][malloc_data]
^______ ___^
| |
[ptr][alloc_id] = "fat pointer"
Defining the allocation_ID as the address of the malloc data structure and placing that at the end of the array earns us a very efficient way to make sure pointer increment (a very frequent operation and source of memory bugs) still points inside of the array, in a single assembly instruction: just CMP the new [ptr] with the [alloc_id]
(for other operations, like pointer arithmetic with negative ints where [ptr] can go down, you would of course need to deference [alloc_id] and obtain the lower limit of the array stored somewhere in the malloc_data structure)
This solves a slew of problems:
- pointer arithmetic can now be performed only when it makes sense (identical alloc_id)
- binary equality of pointers is a guarantee that they point to the same object
- the compiler can easily implement some or more memory protection checks, based on the desired performance-safety trade-off
- the cost in memory or stack space of doubling pointer size should not have a significant impact on most real programs
- no syntax changes should be required
Since this cannot be a new ideea, I would like someone more knowledgeable to poke some holes in it.
[1] https://news.ycombinator.com/item?id=17585357 https://news.ycombinator.com/item?id=17585357
- pjmlp 8y agoIn fact your idea is not new. "Efficient Tagged Memory" http://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201711-iccd2017-efficient-tags.pdf http://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201711-... "SPARC M7 Application Data Integrity" https://swisdev.oracle.com/_files/What-Is-ADI.html https://swisdev.oracle.com/_files/What-Is-ADI.html The problem to most C improvement solutions is mostly human, not technical.
- bumholio 8y agoAs I have said, I'm sure it's not a new concept. You provided some links to hardware accelerators for somewhat related systems, and they imply software solutions are unworkable performance wise. But it seems to me that is not the case for what I am proposing. For the most part, working with pointers should generate almost the same assembly, the [alloc_id] part is simply copied around verbatim and [ptr] is used as before. A function that just dereferences pointer parameters will receive alloc_id in the stack frame but it will ignore it and not load it in the registers. If the pointer is duplicated, the alloc_id is copied on, somewhat increasing stack pressure and reducing memory bandwidth, but certainly not 100x slowdown. Modern processors are very good at parallelising these type of loads and stores. The performance impact should hit when doing pointer arithmetic and advanced casting, depending on the degree of runtime assurance we want to offer. Every address alteration is followed by a sanity check of the pointer against it's allocation segment. An out-of-bounds pointer can be NULLed to trigger a subsequent run-time exception, while keeping with the standard that such pointers mean undefined behavior. In the case of some frequent operations, like incrementing, these checks can be extremely fast. Not that hardware solutions would not help, but if such a technique works there is certainly a class of programs that would even accept the slowdown of a software solution. So I have to wonder if there is more to this I am not seeing, besides performance.
- pjmlp 8y agoWhat you are missing it is the human factor. At CppCon 2014, if I am not mistaken, too lazy to search the exact year. Herb Sutter asked the audience how many use some kind of analysis tooling. About 1% of the audience say they did. Joe Duffy has a remark almost at the end of his keynote at Rustconf where he states even with Midori running in front of the Windows team, they weren't accepting it as possible. At least on Solaris, regardless of its future, those protections are now on for many executables. https://blogs.oracle.com/solaris/default-memory-allocator-security-protections-using-silicon-secured-memory-ssm-adi https://blogs.oracle.com/solaris/default-memory-allocator-se... Likewise Google has been locking down what native code is allowed to do on Android, including compiling everything with FORTIFY enabled. It seems pressure must come from OS vendors for habits to change.
- tom_mellior 8y agoThis is a workable approach. One implementation I know of is CCured: https://people.eecs.berkeley.edu/~necula/Papers/ccured_popl02.pdf https://people.eecs.berkeley.edu/~necula/Papers/ccured_popl0... They claim 0-150% runtime overhead. It depends a lot on concrete characteristics of the program. For a debugging tool that's certainly acceptable.