diff --git a/linker/Android.bp b/linker/Android.bp
index a3b9cb2..29cccf4 100644
--- a/linker/Android.bp
+++ b/linker/Android.bp
@@ -18,6 +18,7 @@
         "linker.cpp",
         "linker_block_allocator.cpp",
         "linker_dlwarning.cpp",
+        "linker_cfi.cpp",
         "linker_gdb_support.cpp",
         "linker_globals.cpp",
         "linker_libc_support.c",
diff --git a/linker/dlfcn.cpp b/linker/dlfcn.cpp
index bb7b1ca..0092179 100644
--- a/linker/dlfcn.cpp
+++ b/linker/dlfcn.cpp
@@ -15,6 +15,7 @@
  */
 
 #include "linker.h"
+#include "linker_cfi.h"
 #include "linker_globals.h"
 #include "linker_dlwarning.h"
 
@@ -189,6 +190,10 @@
   return result;
 }
 
+void __cfi_fail(uint64_t CallSiteTypeId, void* Ptr, void *DiagData, void *CallerPc) {
+  CFIShadowWriter::CfiFail(CallSiteTypeId, Ptr, DiagData, CallerPc);
+}
+
 // name_offset: starting index of the name in libdl_info.strtab
 #define ELF32_SYM_INITIALIZER(name_offset, value, shndx) \
     { name_offset, \
@@ -225,11 +230,11 @@
   // 012345678901234 567890123456789012345678901234567 8901234567890123456789012345678901 2345678901234567 89
     "et_sdk_version\0__loader_android_init_namespaces\0__loader_android_create_namespace\0__loader_dlvsym\0__"
   // 4*
-  // 0000000000111111111122222 2222233333333334444444 4445555555555666666666677777777778 8888888889999999 999
-  // 0123456789012345678901234 5678901234567890123456 7890123456789012345678901234567890 1234567890123456 789
-    "loader_android_dlwarning\0"
+  // 0000000000111111111122222 222223333333333444 4444444555555555566666666667777 77777788888888889999999999
+  // 0123456789012345678901234 567890123456789012 3456789012345678901234567890123 45678901234567890123456789
+    "loader_android_dlwarning\0__loader_cfi_fail\0"
 #if defined(__arm__)
-  // 425
+  // 443
     "__loader_dl_unwind_find_exidx\0"
 #endif
     ;
@@ -255,8 +260,9 @@
   ELFW(SYM_INITIALIZER)(348, &__android_create_namespace, 1),
   ELFW(SYM_INITIALIZER)(382, &__dlvsym, 1),
   ELFW(SYM_INITIALIZER)(398, &__android_dlwarning, 1),
+  ELFW(SYM_INITIALIZER)(425, &__cfi_fail, 1),
 #if defined(__arm__)
-  ELFW(SYM_INITIALIZER)(425, &__dl_unwind_find_exidx, 1),
+  ELFW(SYM_INITIALIZER)(443, &__dl_unwind_find_exidx, 1),
 #endif
 };
 
@@ -273,9 +279,9 @@
 // Note that adding any new symbols here requires stubbing them out in libdl.
 static unsigned g_libdl_buckets[1] = { 1 };
 #if defined(__arm__)
-static unsigned g_libdl_chains[] = { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 0 };
+static unsigned g_libdl_chains[] = { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 0 };
 #else
-static unsigned g_libdl_chains[] = { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };
+static unsigned g_libdl_chains[] = { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 0 };
 #endif
 
 static uint8_t __libdl_info_buf[sizeof(soinfo)] __attribute__((aligned(8)));
diff --git a/linker/linker.cpp b/linker/linker.cpp
index fc8d1ef..83bd9f3 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -48,6 +48,7 @@
 
 #include "linker.h"
 #include "linker_block_allocator.h"
+#include "linker_cfi.h"
 #include "linker_gdb_support.h"
 #include "linker_globals.h"
 #include "linker_debug.h"
@@ -105,6 +106,12 @@
 // Is ASAN enabled?
 static bool g_is_asan = false;
 
+static CFIShadowWriter g_cfi_shadow;
+
+CFIShadowWriter* get_cfi_shadow() {
+  return &g_cfi_shadow;
+}
+
 static bool is_system_library(const std::string& realpath) {
   for (const auto& dir : g_default_namespace.get_default_library_paths()) {
     if (file_is_in_dir(realpath, dir)) {
@@ -1226,7 +1233,7 @@
 //    target_sdk_version (*candidate != nullptr)
 // 2. The library was not found by soname (*candidate is nullptr)
 static bool find_loaded_library_by_soname(android_namespace_t* ns,
-                                          const char* name, soinfo** candidate) {
+                                         const char* name, soinfo** candidate) {
   *candidate = nullptr;
 
   // Ignore filename with path.
@@ -1504,7 +1511,8 @@
 
   bool linked = local_group.visit([&](soinfo* si) {
     if (!si->is_linked()) {
-      if (!si->link_image(global_group, local_group, extinfo)) {
+      if (!si->link_image(global_group, local_group, extinfo) ||
+          !get_cfi_shadow()->AfterLoad(si, solist_get_head())) {
         return false;
       }
     }
@@ -1656,6 +1664,7 @@
 
   while ((si = local_unload_list.pop_front()) != nullptr) {
     notify_gdb_of_unload(si);
+    get_cfi_shadow()->BeforeUnload(si);
     soinfo_free(si);
   }
 
diff --git a/linker/linker.h b/linker/linker.h
index c65d503..7746982 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -103,6 +103,8 @@
 
 soinfo* get_libdl_info(const char* linker_path);
 
+soinfo* find_containing_library(const void* p);
+
 void do_android_get_LD_LIBRARY_PATH(char*, size_t);
 void do_android_update_LD_LIBRARY_PATH(const char* ld_library_path);
 void* do_dlopen(const char* name,
@@ -125,6 +127,10 @@
 
 int do_dladdr(const void* addr, Dl_info* info);
 
+// void ___cfi_slowpath(uint64_t CallSiteTypeId, void *Ptr, void *Ret);
+// void ___cfi_slowpath_diag(uint64_t CallSiteTypeId, void *Ptr, void *DiagData, void *Ret);
+void ___cfi_fail(uint64_t CallSiteTypeId, void* Ptr, void *DiagData, void *Ret);
+
 void set_application_target_sdk_version(uint32_t target);
 uint32_t get_application_target_sdk_version();
 
@@ -163,7 +169,4 @@
                                       const char* permitted_when_isolated_path,
                                       android_namespace_t* parent_namespace);
 
-constexpr unsigned kLibraryAlignmentBits = 18;
-constexpr size_t kLibraryAlignment = 1UL << kLibraryAlignmentBits;
-
 #endif
diff --git a/linker/linker_cfi.cpp b/linker/linker_cfi.cpp
new file mode 100644
index 0000000..f788c16
--- /dev/null
+++ b/linker/linker_cfi.cpp
@@ -0,0 +1,273 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "linker_cfi.h"
+
+#include "linker_debug.h"
+#include "linker_globals.h"
+#include "private/bionic_page.h"
+#include "private/bionic_prctl.h"
+
+#include <sys/mman.h>
+#include <sys/types.h>
+#include <cstdint>
+
+// Update shadow without making it writable by preparing the data on the side and mremap-ing it in
+// place.
+class ShadowWrite {
+  char* shadow_start;
+  char* shadow_end;
+  char* aligned_start;
+  char* aligned_end;
+  char* tmp_start;
+
+ public:
+  ShadowWrite(uint16_t* s, uint16_t* e) {
+    shadow_start = reinterpret_cast<char*>(s);
+    shadow_end = reinterpret_cast<char*>(e);
+    aligned_start = reinterpret_cast<char*>(PAGE_START(reinterpret_cast<uintptr_t>(shadow_start)));
+    aligned_end = reinterpret_cast<char*>(PAGE_END(reinterpret_cast<uintptr_t>(shadow_end)));
+    tmp_start =
+        reinterpret_cast<char*>(mmap(nullptr, aligned_end - aligned_start, PROT_READ | PROT_WRITE,
+                                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0));
+    CHECK(tmp_start != MAP_FAILED);
+    memcpy(tmp_start, aligned_start, shadow_start - aligned_start);
+    memcpy(tmp_start + (shadow_end - aligned_start), shadow_end, aligned_end - shadow_end);
+  }
+
+  uint16_t* begin() {
+    return reinterpret_cast<uint16_t*>(tmp_start + (shadow_start - aligned_start));
+  }
+
+  uint16_t* end() {
+    return reinterpret_cast<uint16_t*>(tmp_start + (shadow_end - aligned_start));
+  }
+
+  ~ShadowWrite() {
+    size_t size = aligned_end - aligned_start;
+    mprotect(tmp_start, size, PROT_READ);
+    void* res = mremap(tmp_start, size, size, MREMAP_MAYMOVE | MREMAP_FIXED,
+                       reinterpret_cast<void*>(aligned_start));
+    CHECK(res != MAP_FAILED);
+  }
+};
+
+void CFIShadowWriter::FixupVmaName() {
+  prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, *shadow_start, kShadowSize, "cfi shadow");
+}
+
+void CFIShadowWriter::AddConstant(uintptr_t begin, uintptr_t end, uint16_t v) {
+  uint16_t* shadow_begin = MemToShadow(begin);
+  uint16_t* shadow_end = MemToShadow(end - 1) + 1;
+
+  ShadowWrite sw(shadow_begin, shadow_end);
+  std::fill(sw.begin(), sw.end(), v);
+}
+
+void CFIShadowWriter::AddUnchecked(uintptr_t begin, uintptr_t end) {
+  AddConstant(begin, end, kUncheckedShadow);
+}
+
+void CFIShadowWriter::AddInvalid(uintptr_t begin, uintptr_t end) {
+  AddConstant(begin, end, kInvalidShadow);
+}
+
+void CFIShadowWriter::Add(uintptr_t begin, uintptr_t end, uintptr_t cfi_check) {
+  CHECK((cfi_check & (kCfiCheckAlign - 1)) == 0);
+
+  // Don't fill anything below cfi_check. We can not represent those addresses
+  // in the shadow, and must make sure at codegen to place all valid call
+  // targets above cfi_check.
+  begin = std::max(begin, cfi_check) & ~(kShadowAlign - 1);
+  uint16_t* shadow_begin = MemToShadow(begin);
+  uint16_t* shadow_end = MemToShadow(end - 1) + 1;
+
+  ShadowWrite sw(shadow_begin, shadow_end);
+  uint16_t sv = ((begin + kShadowAlign - cfi_check) >> kCfiCheckGranularity) + kRegularShadowMin;
+
+  // With each step of the loop below, __cfi_check address computation base is increased by
+  // 2**ShadowGranularity.
+  // To compensate for that, each next shadow value must be increased by 2**ShadowGranularity /
+  // 2**CfiCheckGranularity.
+  uint16_t sv_step = 1 << (kShadowGranularity - kCfiCheckGranularity);
+  for (uint16_t& s : sw) {
+    // If there is something there already, fall back to unchecked. This may happen in rare cases
+    // with MAP_FIXED libraries. FIXME: consider using a (slow) resolution function instead.
+    s = (s == kInvalidShadow) ? sv : kUncheckedShadow;
+    sv += sv_step;
+  }
+}
+
+static soinfo* find_libdl(soinfo* solist) {
+  for (soinfo* si = solist; si != nullptr; si = si->next) {
+    const char* soname = si->get_soname();
+    if (soname && strcmp(soname, "libdl.so") == 0) {
+      return si;
+    }
+  }
+  return nullptr;
+}
+
+static uintptr_t soinfo_find_symbol(soinfo* si, const char* s) {
+  SymbolName name(s);
+  const ElfW(Sym) * sym;
+  if (si->find_symbol_by_name(name, nullptr, &sym) && sym) {
+    return si->resolve_symbol_address(sym);
+  }
+  return 0;
+}
+
+uintptr_t soinfo_find_cfi_check(soinfo* si) {
+  return soinfo_find_symbol(si, "__cfi_check");
+}
+
+uintptr_t CFIShadowWriter::MapShadow() {
+  void* p =
+      mmap(nullptr, kShadowSize, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);
+  CHECK(p != MAP_FAILED);
+  return reinterpret_cast<uintptr_t>(p);
+}
+
+bool CFIShadowWriter::AddLibrary(soinfo* si) {
+  CHECK(shadow_start != nullptr);
+  if (si->base == 0 || si->size == 0) {
+    return true;
+  }
+  uintptr_t cfi_check = soinfo_find_cfi_check(si);
+  if (cfi_check == 0) {
+    INFO("[ CFI add 0x%zx + 0x%zx %s ]", static_cast<uintptr_t>(si->base),
+         static_cast<uintptr_t>(si->size), si->get_soname());
+    AddUnchecked(si->base, si->base + si->size);
+    return true;
+  }
+
+  INFO("[ CFI add 0x%zx + 0x%zx %s: 0x%zx ]", static_cast<uintptr_t>(si->base),
+       static_cast<uintptr_t>(si->size), si->get_soname(), cfi_check);
+#ifdef __arm__
+  // Require Thumb encoding.
+  if ((cfi_check & 1UL) != 1UL) {
+    DL_ERR("__cfi_check in not a Thumb function in the library \"%s\"", si->get_soname());
+    return false;
+  }
+  cfi_check &= ~1UL;
+#endif
+  if ((cfi_check & (kCfiCheckAlign - 1)) != 0) {
+    DL_ERR("unaligned __cfi_check in the library \"%s\"", si->get_soname());
+    return false;
+  }
+  Add(si->base, si->base + si->size, cfi_check);
+  return true;
+}
+
+// Pass the shadow mapping address to libdl.so. In return, we get an pointer to the location
+// libdl.so uses to store the address.
+bool CFIShadowWriter::NotifyLibDl(soinfo* solist, uintptr_t p) {
+  soinfo* libdl = find_libdl(solist);
+  if (libdl == nullptr) {
+    DL_ERR("CFI could not find libdl");
+    return false;
+  }
+
+  uintptr_t cfi_init = soinfo_find_symbol(libdl, "__cfi_init");
+  CHECK(cfi_init != 0);
+  shadow_start = reinterpret_cast<uintptr_t* (*)(uintptr_t)>(cfi_init)(p);
+  CHECK(shadow_start != nullptr);
+  CHECK(*shadow_start == p);
+  return true;
+}
+
+bool CFIShadowWriter::MaybeInit(soinfo* new_si, soinfo* solist) {
+  CHECK(initial_link_done);
+  // Check if CFI shadow must be initialized at this time.
+  bool found = false;
+  if (new_si == nullptr) {
+    // This is the case when we've just completed the initial link. There may have been earlier
+    // calls to MaybeInit that were skipped. Look though the entire solist.
+    for (soinfo* si = solist; si != nullptr; si = si->next) {
+      if (soinfo_find_cfi_check(si)) {
+        found = true;
+        break;
+      }
+    }
+  } else {
+    // See if the new library uses CFI.
+    found = soinfo_find_cfi_check(new_si);
+  }
+
+  // Nothing found.
+  if (!found) {
+    return true;
+  }
+
+  // Init shadow and add all currently loaded libraries (not just the new ones).
+  if (!NotifyLibDl(solist, MapShadow()))
+    return false;
+  for (soinfo* si = solist; si != nullptr; si = si->next) {
+    if (!AddLibrary(si))
+      return false;
+  }
+  FixupVmaName();
+  return true;
+}
+
+bool CFIShadowWriter::AfterLoad(soinfo* si, soinfo* solist) {
+  if (!initial_link_done) {
+    // Too early.
+    return true;
+  }
+
+  if (shadow_start == nullptr) {
+    return MaybeInit(si, solist);
+  }
+
+  // Add the new library to the CFI shadow.
+  if (!AddLibrary(si))
+    return false;
+  FixupVmaName();
+  return true;
+}
+
+void CFIShadowWriter::BeforeUnload(soinfo* si) {
+  if (shadow_start == nullptr) return;
+  if (si->base == 0 || si->size == 0) return;
+  INFO("[ CFI remove 0x%zx + 0x%zx: %s ]", static_cast<uintptr_t>(si->base),
+       static_cast<uintptr_t>(si->size), si->get_soname());
+  AddInvalid(si->base, si->base + si->size);
+  FixupVmaName();
+}
+
+bool CFIShadowWriter::InitialLinkDone(soinfo* solist) {
+  CHECK(!initial_link_done)
+  initial_link_done = true;
+  return MaybeInit(nullptr, solist);
+}
+
+// Find __cfi_check in the caller and let it handle the problem. Since caller_pc is likely not a
+// valid CFI target, we can not use CFI shadow for lookup. This does not need to be fast, do the
+// regular symbol lookup.
+void CFIShadowWriter::CfiFail(uint64_t CallSiteTypeId, void* Ptr, void* DiagData, void* CallerPc) {
+  soinfo* si = find_containing_library(CallerPc);
+  if (!si) {
+    __builtin_trap();
+  }
+
+  uintptr_t cfi_check = soinfo_find_cfi_check(si);
+  if (!cfi_check) {
+    __builtin_trap();
+  }
+
+  reinterpret_cast<CFICheckFn>(cfi_check)(CallSiteTypeId, Ptr, DiagData);
+}
diff --git a/linker/linker_cfi.h b/linker/linker_cfi.h
new file mode 100644
index 0000000..df76421
--- /dev/null
+++ b/linker/linker_cfi.h
@@ -0,0 +1,96 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _LINKER_CFI_H_
+#define _LINKER_CFI_H_
+
+#include "linker.h"
+#include "linker_debug.h"
+
+#include <algorithm>
+
+#include "private/CFIShadow.h"
+
+// This class keeps the contents of CFI shadow up-to-date with the current set of loaded libraries.
+// See the comment in CFIShadow.h for more context.
+// See documentation in http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#shared-library-support.
+//
+// Shadow is mapped and initialized lazily as soon as the first CFI-enabled DSO is loaded.
+// It is updated after a set of libraries is loaded (but before any constructors are ran), and
+// before any library is unloaded.
+class CFIShadowWriter : private CFIShadow {
+  // Returns pointer to the shadow element for an address.
+  uint16_t* MemToShadow(uintptr_t x) {
+    return reinterpret_cast<uint16_t*>(*shadow_start + MemToShadowOffset(x));
+  }
+
+  // Update shadow for the address range to the given constant value.
+  void AddConstant(uintptr_t begin, uintptr_t end, uint16_t v);
+
+  // Update shadow for the address range to kUncheckedShadow.
+  void AddUnchecked(uintptr_t begin, uintptr_t end);
+
+  // Update shadow for the address range to kInvalidShadow.
+  void AddInvalid(uintptr_t begin, uintptr_t end);
+
+  // Update shadow for the address range to the given __cfi_check value.
+  void Add(uintptr_t begin, uintptr_t end, uintptr_t cfi_check);
+
+  // Add a DSO to CFI shadow.
+  bool AddLibrary(soinfo* si);
+
+  // Map CFI shadow.
+  uintptr_t MapShadow();
+
+  // Initialize CFI shadow and update its contents for everything in solist if any loaded library is
+  // CFI-enabled. If soinfos != nullptr, do an incremental check by looking only at the libraries in
+  // soinfos[]; otherwise look at the entire solist.
+  //
+  // Returns false if the shadow is already initialized. It is the caller's responsibility to update
+  // the shadow for the new libraries in that case.
+  // Otherwise, returns true and leaves the shadow either up-to-date or uninitialized.
+  bool MaybeInit(soinfo *new_si, soinfo *solist);
+
+  // Set a human readable name for the entire shadow region.
+  void FixupVmaName();
+
+  bool NotifyLibDl(soinfo *solist, uintptr_t p);
+
+  // Pointer to the shadow start address.
+  uintptr_t *shadow_start;
+
+  bool initial_link_done;
+
+ public:
+  // Update shadow after loading a set of DSOs.
+  // This function will initialize the shadow if it sees a CFI-enabled DSO for the first time.
+  // In that case it will retroactively update shadow for all previously loaded DSOs. "solist" is a
+  // pointer to the global list.
+  // This function must be called before any user code has observed the newly loaded DSO.
+  bool AfterLoad(soinfo* si, soinfo *solist);
+
+  // Update shadow before unloading a DSO.
+  void BeforeUnload(soinfo* si);
+
+  bool InitialLinkDone(soinfo *solist);
+
+  // Handle failure to locate __cfi_check for a target address.
+  static void CfiFail(uint64_t CallSiteTypeId, void* Ptr, void* DiagData, void *caller_pc);
+};
+
+CFIShadowWriter* get_cfi_shadow();
+
+#endif // _LINKER_CFI_H_
diff --git a/linker/linker_main.cpp b/linker/linker_main.cpp
index dad7409..3a2f35b 100644
--- a/linker/linker_main.cpp
+++ b/linker/linker_main.cpp
@@ -29,6 +29,7 @@
 #include "linker_main.h"
 
 #include "linker_debug.h"
+#include "linker_cfi.h"
 #include "linker_gdb_support.h"
 #include "linker_globals.h"
 #include "linker_phdr.h"
@@ -368,6 +369,10 @@
 
   add_vdso(args);
 
+  if (!get_cfi_shadow()->InitialLinkDone(solist)) {
+    __libc_fatal("CANNOT LINK EXECUTABLE \"%s\": %s", g_argv[0], linker_get_error_buffer());
+  }
+
   {
     ProtectedDataGuard guard;
 
diff --git a/linker/linker_phdr.cpp b/linker/linker_phdr.cpp
index a453bef..72549cc 100644
--- a/linker/linker_phdr.cpp
+++ b/linker/linker_phdr.cpp
@@ -42,6 +42,7 @@
 #include "linker_utils.h"
 
 #include "private/bionic_prctl.h"
+#include "private/CFIShadow.h" // For kLibraryAlignment
 
 static int GetTargetElfMachine() {
 #if defined(__arm__)