Adve, Vikram Sadanand via llvm-dev
2020-Jan-07 14:44 UTC
[llvm-dev] Best way of implement a fat pointer for C
Jie, Do you actually want a fat-pointer specifically, or do you just want an efficient way to associate metadata with C pointers? Because (as I‘m sure you know) fat pointers have serious compatibility problems with external libraries, and also may break C programs in other ways due to lack of sound type information. John Criswell (copied) had created an improved version of Baggy Bounds which gives a efficient and compatible solution at low memory overhead. I suggest contacting him if you’re interested. —Vikram Adve + Donald B. Gillies Professor of Computer Science, University of Illinois at Urbana-Champaign + Admin: Kimberly Baker – kabaker at illinois.edu<mailto:kabaker at illinois.edu> + Skype: vikramadve || Zoom: https://zoom.us/j/2173900467 + Home page: http://vikram.cs.illinois.edu + Center for Digital Agriculture: https://digitalag.illinois.edu<https://digitalag.illinois.edu/> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of via llvm-dev <llvm-dev at lists.llvm.org> Reply-To: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org>, "llvm-dev-request at lists.llvm.org" <llvm-dev-request at lists.llvm.org> Date: Tuesday, January 7, 2020 at 8:06 AM To: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org> Subject: llvm-dev Digest, Vol 187, Issue 17 Date: Tue, 7 Jan 2020 02:45:01 +0000 From: Jie Zhou via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> To: Eli Friedman via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> Subject: [llvm-dev] Best way of implement a fat pointer for C Message-ID: <B6510CF7-CC75-4171-AF50-D6730EB068E8 at cs.rochester.edu<mailto:B6510CF7-CC75-4171-AF50-D6730EB068E8 at cs.rochester.edu>> Content-Type: text/plain; charset="utf-8" Dear All, I’m working on a project that extends C. I’m adding a new type of pointer that is a fat pointer. It has some metadata about the pointed object besides the starting address of the object. Currently I implemented this pointer as an llvm:StructType. In llvm::Type generation function llvm::Type *CodeGenTypes::ConvertType(QualType T) in the case for clang::Type::Pointer, instead of creating an llvm::PointerType I create an llvm::StructType type for this new type of pointer. And I added some helper code in llvm::StructType and in multiple places I added code to trick the compiler to believe sometimes a struct is actually a pointer. Until now it compile test programs fine with -O0 but I got lots of assertion failures when compiling with -O1 or -O2 majorly because of the confusion of type mismatch. LLVM assumes that a PointerType is essentially an Integer (32 or 64 bit depending on the architecture), and since this is quite a fundamental assumption, I started to question whether my way of implementing the fat pointer is feasible. I thought about adding a new llvm type that inherits both llvm:PointerType and llvm:StructType; but I’m not sure if this is the correct path. It looks like this demands substantial changes to the compiler including adding code for bitcode generation. Can you give me some advice on how to implement a fat pointer in llvm? Thanks, - Jie -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200107/3fe60169/attachment-0001.html> -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200107/ff1dc981/attachment.html>
Jie Zhou via llvm-dev
2020-Jan-07 15:42 UTC
[llvm-dev] Best way of implement a fat pointer for C
Hi Vikram, I’m working on the Checked C project (https://www.microsoft.com/en-us/research/project/checked-c/) to enhance it with temporal memory safety. Fundamentally we want an (super) efficient way (ideally with less than 5% performance overhead) of associating metadata with C pointers, and the reason we chose fat pointer is we believe this would be the most efficient way, although at the cost of breaking the backward compatibility. I’ve done a literature survey and found that most solutions (e.g., CETS, DANGNULL, FreeSentry, DangSan, etc) use disjoint data structures to keep track of the point-to relations and maintaining the data structures is where all the overhead (both performance and memory) comes from, and none of the existing solutions are fast enough. I worked on this project last summer at Microsoft with David Tarditi, and our conclusion is that fat pointer is the way to go if speed and memory consumption are more critical issues than compatibility. Actually I’ve discussed this issue with John and we have received a small grant from Microsoft Research with the "fat-pointer” design in the proposal (John is my advisor at Rochester :-)) . John talked about implementing the fat pointer using an llvm vector or 128-bit integer, but we would still have the type mismatch problem because in lots of places the compiler is expecting an llvm::PointerType. I’ll discuss this more with John. Thanks, - Jie On Jan 7, 2020, at 09:44, Adve, Vikram Sadanand via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote: Jie, Do you actually want a fat-pointer specifically, or do you just want an efficient way to associate metadata with C pointers? Because (as I‘m sure you know) fat pointers have serious compatibility problems with external libraries, and also may break C programs in other ways due to lack of sound type information. John Criswell (copied) had created an improved version of Baggy Bounds which gives a efficient and compatible solution at low memory overhead. I suggest contacting him if you’re interested. —Vikram Adve + Donald B. Gillies Professor of Computer Science, University of Illinois at Urbana-Champaign + Admin: Kimberly Baker – kabaker at illinois.edu<mailto:kabaker at illinois.edu> + Skype: vikramadve || Zoom: https://zoom.us/j/2173900467<https://urldefense.proofpoint.com/v2/url?u=https-3A__zoom.us_j_2173900467&d=DwMGaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=KAtyTEI8n3FritxDpKpR7rv3VjdmUs0luiVKZLb_bNI&m=kwZQV6kYBqMJiQ-hUwT6xk1CwdZ_yKG_ydk5ktG8LjE&s=R6GhCyK2NtwIS_pzSpGJ2VoASoZdYib5wtfk0eSuJhk&e=> + Home page: http://vikram.cs.illinois.edu<https://urldefense.proofpoint.com/v2/url?u=http-3A__vikram.cs.illinois.edu&d=DwMGaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=KAtyTEI8n3FritxDpKpR7rv3VjdmUs0luiVKZLb_bNI&m=kwZQV6kYBqMJiQ-hUwT6xk1CwdZ_yKG_ydk5ktG8LjE&s=9mEHtkFIqi1LIJd-W9G5gbbTfGcWup7PfDIDSC6thVk&e=> + Center for Digital Agriculture: https://digitalag.illinois.edu<https://urldefense.proofpoint.com/v2/url?u=https-3A__digitalag.illinois.edu_&d=DwMGaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=KAtyTEI8n3FritxDpKpR7rv3VjdmUs0luiVKZLb_bNI&m=kwZQV6kYBqMJiQ-hUwT6xk1CwdZ_yKG_ydk5ktG8LjE&s=nanGYamM8MpQFTfvLj9klIViM3Nx-u2RywioB3rYx-U&e=> From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces at lists.llvm.org>> on behalf of via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> Reply-To: "llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>" <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>, "llvm-dev-request at lists.llvm.org<mailto:llvm-dev-request at lists.llvm.org>" <llvm-dev-request at lists.llvm.org<mailto:llvm-dev-request at lists.llvm.org>> Date: Tuesday, January 7, 2020 at 8:06 AM To: "llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>" <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> Subject: llvm-dev Digest, Vol 187, Issue 17 Date: Tue, 7 Jan 2020 02:45:01 +0000 From: Jie Zhou via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> To: Eli Friedman via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> Subject: [llvm-dev] Best way of implement a fat pointer for C Message-ID: <B6510CF7-CC75-4171-AF50-D6730EB068E8 at cs.rochester.edu<mailto:B6510CF7-CC75-4171-AF50-D6730EB068E8 at cs.rochester.edu>> Content-Type: text/plain; charset="utf-8" Dear All, I’m working on a project that extends C. I’m adding a new type of pointer that is a fat pointer. It has some metadata about the pointed object besides the starting address of the object. Currently I implemented this pointer as an llvm:StructType. In llvm::Type generation function llvm::Type *CodeGenTypes::ConvertType(QualType T) in the case for clang::Type::Pointer, instead of creating an llvm::PointerType I create an llvm::StructType type for this new type of pointer. And I added some helper code in llvm::StructType and in multiple places I added code to trick the compiler to believe sometimes a struct is actually a pointer. Until now it compile test programs fine with -O0 but I got lots of assertion failures when compiling with -O1 or -O2 majorly because of the confusion of type mismatch. LLVM assumes that a PointerType is essentially an Integer (32 or 64 bit depending on the architecture), and since this is quite a fundamental assumption, I started to question whether my way of implementing the fat pointer is feasible. I thought about adding a new llvm type that inherits both llvm:PointerType and llvm:StructType; but I’m not sure if this is the correct path. It looks like this demands substantial changes to the compiler including adding code for bitcode generation. Can you give me some advice on how to implement a fat pointer in llvm? Thanks, - Jie -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200107/3fe60169/attachment-0001.html<https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_pipermail_llvm-2Ddev_attachments_20200107_3fe60169_attachment-2D0001.html&d=DwMGaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=KAtyTEI8n3FritxDpKpR7rv3VjdmUs0luiVKZLb_bNI&m=kwZQV6kYBqMJiQ-hUwT6xk1CwdZ_yKG_ydk5ktG8LjE&s=bjlqJQjQoad75TLdBCeW4uVHCd6riLNojVTKyvg7G5M&e=>> _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwIGaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r=KAtyTEI8n3FritxDpKpR7rv3VjdmUs0luiVKZLb_bNI&m=kwZQV6kYBqMJiQ-hUwT6xk1CwdZ_yKG_ydk5ktG8LjE&s=u5oJBUPGpLf1PPp7CE54c9iqUq_2loVCQS6-U8gWEo0&e -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200107/862661b6/attachment.html>