[llvm-dev] Best way of implement a fat pointer for C

Tue Jan 7 07:42:14 PST 2020

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>