4 ms·

Super cool project. Sorry if you explained this already, I don't know what "Dijkstra accurate" means. How does it know if an object is truly available to be rec

Super cool project. Sorry if you explained this already, I don't know what "Dijkstra accurate" means. How does it know if an object is truly available to be reclaimed, given that pointers can be converted to integers?

pizlonator 1y ago
> given that pointers can be converted to integers? Because if they get converted to integers and then stored to the heap then they lose their capability. So accesses to them will trap and the GC doesn’t need to care about them. Also it’s not “Dijkstra accurate”. It’s a Dijkstra collector in the sense that it uses a Dijkstra barrier. And it’s an accurate collector. But these are orthogonal things
- charleslmunger 1y ago
  Out of curiosity, does this idiom work in fil-c? https://github.com/protocolbuffers/protobuf/blob/cb873c8987dd33282125ecbbae378b74be5f4707/upb/wire/eps_copy_input_stream.h#L286 https://github.com/protocolbuffers/protobuf/blob/cb873c8987d... // This somewhat silly looking add-and-subtract behavior provides provenance // from the original input buffer's pointer. After optimization it produces // the same assembly as just casting `(uintptr_t)ptr+input_delta` // https://godbolt.org/z/zosG88oPn size_t position = (uintptr_t)ptr + e->input_delta - (uintptr_t)e->buffer_start; return e->buffer_start + position; It does use the implementation defined behavior that a char pointer + 1 casted to uintptr is the same as casting to uintptr then adding 1.
  - pizlonator 1y ago
    Yeah that should just work Code that strives to preserve provenance works in Fil-C
    - charleslmunger 1y ago
      Very cool. Hardware asan did not catch the pointer provenance bug in the previous implementation of that code because it relies on tag bits, and the produced pointer was bit-identical to the intended one. It sounds like fil-c would have caught it because the pointer capabilities are stored elsewhere.
      - kragen 1y ago
        What hardware do you need for hardware Asan? I'm so out of the loop that I haven't heard of it before.
        saagarjha 1y ago
        TBI: https://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html https://clang.llvm.org/docs/HardwareAssistedAddressSanitizer...
        kragen 1y ago
        Thanks!
- AndyKelley 1y ago
  Hmm, I'm still not understanding the bit of information that I'm trying to ask about. Let's say I malloc(42) then print the address to stdout, and then do not otherwise do anything with the pointer. Ten minutes later I prompt the user for an integer, they type back the same address, and then I try to write 42 bytes to that address. What happens? Edit: ok I read up on GC literature briefly and I believe I understand the situation. "conservative" means the garbage collector does not have access to language type system information and is just guessing that every pointer sized thing in the stack is probably a pointer. "accurate" means the compiler tells the GC about pointer types, so it knows about all the pointers the type system knows about. Neither of these are capable of correctly modeling the C language semantics, which allows ptrtoint / inttoptr. So if there are any tricks being used like xor linked lists, storing extra data inside unused pointer alignment bits, or a memory allocator implementation, these will be incompatible even with an "accurate" garbage collector such as this. I should add, this is not a criticism, I'm just trying to understand the design space. It's a pretty compelling trade offer: give up ptrtoint, receive GC.
  - cgh 1y ago
    To expand on the capabilities thing: https://fil-c.org/invisicaps_by_example https://fil-c.org/invisicaps_by_example In particular, check out the sections called "Laundering Pointers As Integers" and "Laundering Integers As Pointers".
    - AndyKelley 1y ago
      Thanks! > This is because the capability is not stored at any addresses that are accessible to the Fil-C program. How are they stored? Is the GC running in a different process?
  - dan-robertson 1y ago
    I think the answer in your example is that when you cast the int into a pointer, it won’t have any capabilities (the other big Fil-C feature?) and therefore you can’t access memory through it.
shim__ 1y ago
Pointers are always integers, which can be interpreted as pointers.

pizlonator 1y ago

> given that pointers can be converted to integers? Because if they get converted to integers and then stored to the heap then they lose their capability. So accesses to them will trap and the GC doesn’t need to care about them. Also it’s not “Dijkstra accurate”. It’s a Dijkstra collector in the sense that it uses a Dijkstra barrier. And it’s an accurate collector. But these are orthogonal things

charleslmunger 1y ago
Out of curiosity, does this idiom work in fil-c? https://github.com/protocolbuffers/protobuf/blob/cb873c8987dd33282125ecbbae378b74be5f4707/upb/wire/eps_copy_input_stream.h#L286 https://github.com/protocolbuffers/protobuf/blob/cb873c8987d... // This somewhat silly looking add-and-subtract behavior provides provenance // from the original input buffer's pointer. After optimization it produces // the same assembly as just casting `(uintptr_t)ptr+input_delta` // https://godbolt.org/z/zosG88oPn size_t position = (uintptr_t)ptr + e->input_delta - (uintptr_t)e->buffer_start; return e->buffer_start + position; It does use the implementation defined behavior that a char pointer + 1 casted to uintptr is the same as casting to uintptr then adding 1.
- pizlonator 1y ago
  Yeah that should just work Code that strives to preserve provenance works in Fil-C
  - charleslmunger 1y ago
    Very cool. Hardware asan did not catch the pointer provenance bug in the previous implementation of that code because it relies on tag bits, and the produced pointer was bit-identical to the intended one. It sounds like fil-c would have caught it because the pointer capabilities are stored elsewhere.
    - kragen 1y ago
      What hardware do you need for hardware Asan? I'm so out of the loop that I haven't heard of it before.
      - saagarjha 1y ago
        TBI: https://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html https://clang.llvm.org/docs/HardwareAssistedAddressSanitizer...
        kragen 1y ago
        Thanks!
AndyKelley 1y ago
Hmm, I'm still not understanding the bit of information that I'm trying to ask about. Let's say I malloc(42) then print the address to stdout, and then do not otherwise do anything with the pointer. Ten minutes later I prompt the user for an integer, they type back the same address, and then I try to write 42 bytes to that address. What happens? Edit: ok I read up on GC literature briefly and I believe I understand the situation. "conservative" means the garbage collector does not have access to language type system information and is just guessing that every pointer sized thing in the stack is probably a pointer. "accurate" means the compiler tells the GC about pointer types, so it knows about all the pointers the type system knows about. Neither of these are capable of correctly modeling the C language semantics, which allows ptrtoint / inttoptr. So if there are any tricks being used like xor linked lists, storing extra data inside unused pointer alignment bits, or a memory allocator implementation, these will be incompatible even with an "accurate" garbage collector such as this. I should add, this is not a criticism, I'm just trying to understand the design space. It's a pretty compelling trade offer: give up ptrtoint, receive GC.
- cgh 1y ago
  To expand on the capabilities thing: https://fil-c.org/invisicaps_by_example https://fil-c.org/invisicaps_by_example In particular, check out the sections called "Laundering Pointers As Integers" and "Laundering Integers As Pointers".
  - AndyKelley 1y ago
    Thanks! > This is because the capability is not stored at any addresses that are accessible to the Fil-C program. How are they stored? Is the GC running in a different process?
- dan-robertson 1y ago
  I think the answer in your example is that when you cast the int into a pointer, it won’t have any capabilities (the other big Fil-C feature?) and therefore you can’t access memory through it.

shim__ 1y ago

Pointers are always integers, which can be interpreted as pointers.