diff --git a/lib/eu-search.c b/lib/eu-search.c
index fc31fe87..a49d8dd3 100644
--- a/lib/eu-search.c
+++ b/lib/eu-search.c
@@ -62,6 +62,24 @@ void *eu_tdelete (const void *key, search_tree *tree,
   return ret;
 }
 
+void *eu_tsearch_nolock (const void *key, search_tree *tree,
+			 int (*compare)(const void *, const void *))
+{
+  return tsearch (key, &tree->root, compare);
+}
+
+void *eu_tfind_nolock (const void *key, search_tree *tree,
+		       int (*compare)(const void *, const void *))
+{
+  return tfind (key, &tree->root, compare);
+}
+
+void *eu_tdelete_nolock (const void *key, search_tree *tree,
+			 int (*compare)(const void *, const void *))
+{
+  return tdelete (key, &tree->root, compare);
+}
+
 void eu_tdestroy (search_tree *tree, void (*free_node)(void *))
 {
   rwlock_wrlock (tree->lock);
diff --git a/lib/eu-search.h b/lib/eu-search.h
index 67b54c18..841a7f64 100644
--- a/lib/eu-search.h
+++ b/lib/eu-search.h
@@ -52,6 +52,18 @@ extern void *eu_tfind (const void *key, search_tree *tree,
 extern void *eu_tdelete (const void *key, search_tree *tree,
 		         int (*compare)(const void *, const void *));
 
+/* Search TREE for KEY and add KEY if not found.  No locking is performed.  */
+extern void *eu_tsearch_nolock (const void *key, search_tree *tree,
+				int (*compare)(const void *, const void *));
+
+/* Search TREE for KEY.  No locking is performed.  */
+extern void *eu_tfind_nolock (const void *key, search_tree *tree,
+			      int (*compare)(const void *, const void *));
+
+/* Delete key from TREE.  No locking is performed.  */
+extern void *eu_tdelete_nolock (const void *key, search_tree *tree,
+				int (*compare)(const void *, const void *));
+
 /* Free all nodes from TREE.  */
 void eu_tdestroy (search_tree *tree, void (*free_node)(void *));
 
diff --git a/libdw/cfi.h b/libdw/cfi.h
index d0134243..f0296de7 100644
--- a/libdw/cfi.h
+++ b/libdw/cfi.h
@@ -98,6 +98,10 @@ struct Dwarf_CFI_s
   /* Search tree for parsed DWARF expressions, indexed by raw pointer.  */
   search_tree expr_tree;
 
+  /* Should be held when calling __libdw_find_fde, __libdw_fde_by_offset and
+     when __libdw_intern_expression is called with Dwarf_CFI members.  */
+  mutex_define(, lock);
+
   /* Backend hook.  */
   struct ebl *ebl;
 
diff --git a/libdw/dwarf_begin_elf.c b/libdw/dwarf_begin_elf.c
index 58a309e9..63e2805d 100644
--- a/libdw/dwarf_begin_elf.c
+++ b/libdw/dwarf_begin_elf.c
@@ -359,6 +359,11 @@ valid_p (Dwarf *result)
 	  result->fake_loc_cu->version = 4;
 	  result->fake_loc_cu->split = NULL;
 	  eu_search_tree_init (&result->fake_loc_cu->locs_tree);
+	  rwlock_init (result->fake_loc_cu->abbrev_lock);
+	  rwlock_init (result->fake_loc_cu->split_lock);
+	  mutex_init (result->fake_loc_cu->src_lock);
+	  mutex_init (result->fake_loc_cu->str_off_base_lock);
+	  mutex_init (result->fake_loc_cu->intern_lock);
 	}
     }
 
@@ -387,6 +392,11 @@ valid_p (Dwarf *result)
 	  result->fake_loclists_cu->version = 5;
 	  result->fake_loclists_cu->split = NULL;
 	  eu_search_tree_init (&result->fake_loclists_cu->locs_tree);
+	  rwlock_init (result->fake_loclists_cu->abbrev_lock);
+	  rwlock_init (result->fake_loclists_cu->split_lock);
+	  mutex_init (result->fake_loclists_cu->src_lock);
+	  mutex_init (result->fake_loclists_cu->str_off_base_lock);
+	  mutex_init (result->fake_loclists_cu->intern_lock);
 	}
     }
 
@@ -420,6 +430,11 @@ valid_p (Dwarf *result)
 	  result->fake_addr_cu->version = 5;
 	  result->fake_addr_cu->split = NULL;
 	  eu_search_tree_init (&result->fake_addr_cu->locs_tree);
+	  rwlock_init (result->fake_addr_cu->abbrev_lock);
+	  rwlock_init (result->fake_addr_cu->split_lock);
+	  mutex_init (result->fake_addr_cu->src_lock);
+	  mutex_init (result->fake_addr_cu->str_off_base_lock);
+	  mutex_init (result->fake_addr_cu->intern_lock);
 	}
     }
 
diff --git a/libdw/dwarf_cfi_addrframe.c b/libdw/dwarf_cfi_addrframe.c
index 44240279..f391f9f9 100644
--- a/libdw/dwarf_cfi_addrframe.c
+++ b/libdw/dwarf_cfi_addrframe.c
@@ -39,7 +39,10 @@ dwarf_cfi_addrframe (Dwarf_CFI *cache, Dwarf_Addr address, Dwarf_Frame **frame)
   if (cache == NULL)
     return -1;
 
+  mutex_lock (cache->lock);
   struct dwarf_fde *fde = __libdw_find_fde (cache, address);
+  mutex_unlock (cache->lock);
+
   if (fde == NULL)
     return -1;
 
diff --git a/libdw/dwarf_end.c b/libdw/dwarf_end.c
index 1628e448..979b1168 100644
--- a/libdw/dwarf_end.c
+++ b/libdw/dwarf_end.c
@@ -61,17 +61,19 @@ static void
 cu_free (void *arg)
 {
   struct Dwarf_CU *p = (struct Dwarf_CU *) arg;
+
   eu_search_tree_fini (&p->locs_tree, noop_free);
+  rwlock_fini (p->abbrev_lock);
+  rwlock_fini (p->split_lock);
+  mutex_fini (p->src_lock);
+  mutex_fini (p->str_off_base_lock);
+  mutex_fini (p->intern_lock);
 
   /* Only free the CU internals if its not a fake CU.  */
   if (p != p->dbg->fake_loc_cu && p != p->dbg->fake_loclists_cu
      && p != p->dbg->fake_addr_cu)
     {
       Dwarf_Abbrev_Hash_free (&p->abbrev_hash);
-      rwlock_fini (p->abbrev_lock);
-      rwlock_fini (p->split_lock);
-      mutex_fini (p->src_lock);
-      mutex_fini (p->str_off_base_lock);
 
       /* Free split dwarf one way (from skeleton to split).  */
       if (p->unit_type == DW_UT_skeleton
diff --git a/libdw/dwarf_frame_cfa.c b/libdw/dwarf_frame_cfa.c
index 07f998cd..c18ee499 100644
--- a/libdw/dwarf_frame_cfa.c
+++ b/libdw/dwarf_frame_cfa.c
@@ -57,11 +57,13 @@ dwarf_frame_cfa (Dwarf_Frame *fs, Dwarf_Op **ops, size_t *nops)
 
     case cfa_expr:
       /* Parse the expression into internal form.  */
+      mutex_lock (fs->cache->lock);
       result = __libdw_intern_expression
 	(NULL, fs->cache->other_byte_order,
 	 fs->cache->e_ident[EI_CLASS] == ELFCLASS32 ? 4 : 8, 4,
 	 &fs->cache->expr_tree, &fs->cfa_data.expr, false, false,
 	 ops, nops, IDX_debug_frame);
+      mutex_unlock (fs->cache->lock);
       break;
 
     case cfa_invalid:
diff --git a/libdw/dwarf_frame_register.c b/libdw/dwarf_frame_register.c
index a6b7c4c1..dbd7f1b2 100644
--- a/libdw/dwarf_frame_register.c
+++ b/libdw/dwarf_frame_register.c
@@ -109,12 +109,16 @@ dwarf_frame_register (Dwarf_Frame *fs, int regno, Dwarf_Op ops_mem[3],
 	block.data = (void *) p;
 
 	/* Parse the expression into internal form.  */
-	if (__libdw_intern_expression (NULL,
-				       fs->cache->other_byte_order,
-				       address_size, 4,
-				       &fs->cache->expr_tree, &block,
-				       true, reg->rule == reg_val_expression,
-				       ops, nops, IDX_debug_frame) < 0)
+	mutex_lock (fs->cache->lock);
+	int res = __libdw_intern_expression (NULL,
+					     fs->cache->other_byte_order,
+					     address_size, 4,
+					     &fs->cache->expr_tree, &block,
+					     true, reg->rule == reg_val_expression,
+					     ops, nops, IDX_debug_frame);
+	mutex_unlock (fs->cache->lock);
+
+	if (res < 0)
 	  return -1;
 	break;
       }
diff --git a/libdw/dwarf_getcfi.c b/libdw/dwarf_getcfi.c
index a4497152..893e3c74 100644
--- a/libdw/dwarf_getcfi.c
+++ b/libdw/dwarf_getcfi.c
@@ -70,6 +70,7 @@ dwarf_getcfi (Dwarf *dbg)
       eu_search_tree_init (&cfi->cie_tree);
       eu_search_tree_init (&cfi->fde_tree);
       eu_search_tree_init (&cfi->expr_tree);
+      mutex_init (cfi->lock);
 
       cfi->ebl = NULL;
 
diff --git a/libdw/dwarf_getlocation.c b/libdw/dwarf_getlocation.c
index ad1d46ca..2a2fd665 100644
--- a/libdw/dwarf_getlocation.c
+++ b/libdw/dwarf_getlocation.c
@@ -154,7 +154,7 @@ store_implicit_value (Dwarf *dbg, search_tree *cache, Dwarf_Op *op)
   block->addr = op;
   block->data = (unsigned char *) data;
   block->length = op->number;
-  if (unlikely (eu_tsearch (block, cache, loc_compare) == NULL))
+  if (unlikely (eu_tsearch_nolock (block, cache, loc_compare) == NULL))
     return 1;
   return 0;
 }
@@ -216,27 +216,38 @@ is_constant_offset (Dwarf_Attribute *attr,
 
   if (found == NULL)
     {
-      Dwarf_Word offset;
-      if (INTUSE(dwarf_formudata) (attr, &offset) != 0)
-	return -1;
+      mutex_lock (attr->cu->intern_lock);
+
+      found = eu_tfind_nolock (&fake, &attr->cu->locs_tree, loc_compare);
+      if (found == NULL)
+	{
+	  Dwarf_Word offset;
+	  if (INTUSE(dwarf_formudata) (attr, &offset) != 0)
+	    {
+	      mutex_unlock (attr->cu->intern_lock);
+	      return -1;
+	    }
 
-      Dwarf_Op *result = libdw_alloc (attr->cu->dbg,
-				      Dwarf_Op, sizeof (Dwarf_Op), 1);
+	  Dwarf_Op *result = libdw_alloc (attr->cu->dbg,
+					  Dwarf_Op, sizeof (Dwarf_Op), 1);
 
-      result->atom = DW_OP_plus_uconst;
-      result->number = offset;
-      result->number2 = 0;
-      result->offset = 0;
+	  result->atom = DW_OP_plus_uconst;
+	  result->number = offset;
+	  result->number2 = 0;
+	  result->offset = 0;
 
-      /* Insert a record in the search tree so we can find it again later.  */
-      struct loc_s *newp = libdw_alloc (attr->cu->dbg,
-					struct loc_s, sizeof (struct loc_s),
-					1);
-      newp->addr = attr->valp;
-      newp->loc = result;
-      newp->nloc = 1;
+	  /* Insert a record in the search tree so we can find it again later.  */
+	  struct loc_s *newp = libdw_alloc (attr->cu->dbg,
+					    struct loc_s, sizeof (struct loc_s),
+					    1);
+	  newp->addr = attr->valp;
+	  newp->loc = result;
+	  newp->nloc = 1;
+
+	  found = eu_tsearch_nolock (newp, &attr->cu->locs_tree, loc_compare);
+	}
 
-      found = eu_tsearch (newp, &attr->cu->locs_tree, loc_compare);
+      mutex_unlock (attr->cu->intern_lock);
     }
 
   assert ((*found)->nloc == 1);
@@ -267,7 +278,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
 
   /* Check whether we already looked at this list.  */
   struct loc_s fake = { .addr = block->data };
-  struct loc_s **found = eu_tfind (&fake, cache, loc_compare);
+  struct loc_s **found = eu_tfind_nolock (&fake, cache, loc_compare);
   if (found != NULL)
     {
       /* We already saw it.  */
@@ -656,7 +667,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
   newp->addr = block->data;
   newp->loc = result;
   newp->nloc = *listlen;
-  eu_tsearch (newp, cache, loc_compare);
+  eu_tsearch_nolock (newp, cache, loc_compare);
 
   /* We did it.  */
   return 0;
@@ -674,13 +685,17 @@ getlocation (struct Dwarf_CU *cu, const Dwarf_Block *block,
       return 0;
     }
 
-  return __libdw_intern_expression (cu->dbg, cu->dbg->other_byte_order,
-				    cu->address_size, (cu->version == 2
-						       ? cu->address_size
-						       : cu->offset_size),
-				    &cu->locs_tree, block,
-				    false, false,
-				    llbuf, listlen, sec_index);
+  mutex_lock (cu->intern_lock);
+  int res = __libdw_intern_expression (cu->dbg, cu->dbg->other_byte_order,
+				       cu->address_size, (cu->version == 2
+							  ? cu->address_size
+							  : cu->offset_size),
+				       &cu->locs_tree, block,
+				       false, false,
+				       llbuf, listlen, sec_index);
+  mutex_unlock (cu->intern_lock);
+
+  return res;
 }
 
 int
diff --git a/libdw/dwarf_getmacros.c b/libdw/dwarf_getmacros.c
index f1c831fa..d7ed7b58 100644
--- a/libdw/dwarf_getmacros.c
+++ b/libdw/dwarf_getmacros.c
@@ -322,15 +322,29 @@ cache_op_table (Dwarf *dbg, int sec_index, Dwarf_Off macoff,
   if (found != NULL)
     return *found;
 
+  mutex_lock (dbg->macro_lock);
+
+  found = eu_tfind_nolock (&fake, &dbg->macro_ops_tree, macro_op_compare);
+  if (found != NULL)
+    {
+      mutex_unlock (dbg->macro_lock);
+      return *found;
+    }
+
   Dwarf_Macro_Op_Table *table = sec_index == IDX_debug_macro
     ? get_table_for_offset (dbg, macoff, startp, endp, cudie)
     : get_macinfo_table (dbg, macoff, cudie);
 
   if (table == NULL)
-    return NULL;
+    {
+      mutex_unlock (dbg->macro_lock);
+      return NULL;
+    }
+
+  Dwarf_Macro_Op_Table **ret = eu_tsearch_nolock (table, &dbg->macro_ops_tree,
+						  macro_op_compare);
+  mutex_unlock (dbg->macro_lock);
 
-  Dwarf_Macro_Op_Table **ret = eu_tsearch (table, &dbg->macro_ops_tree,
-					macro_op_compare);
   if (unlikely (ret == NULL))
     {
       __libdw_seterrno (DWARF_E_NOMEM);
diff --git a/libdw/fde.c b/libdw/fde.c
index a5167805..7f36c4a9 100644
--- a/libdw/fde.c
+++ b/libdw/fde.c
@@ -122,7 +122,8 @@ intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
     fde->instructions += cie->fde_augmentation_data_size;
 
   /* Add the new entry to the search tree.  */
-  struct dwarf_fde **tres = eu_tsearch (fde, &cache->fde_tree, &compare_fde);
+  struct dwarf_fde **tres = eu_tsearch_nolock (fde, &cache->fde_tree,
+					       &compare_fde);
   if (tres == NULL)
     {
       free (fde);
@@ -252,7 +253,8 @@ __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
   /* Look for a cached FDE covering this address.  */
 
   const struct dwarf_fde fde_key = { .start = address, .end = 0 };
-  struct dwarf_fde **found = eu_tfind (&fde_key, &cache->fde_tree, &compare_fde);
+  struct dwarf_fde **found = eu_tfind_nolock (&fde_key, &cache->fde_tree,
+					      &compare_fde);
   if (found != NULL)
     return *found;
 
diff --git a/libdw/frame-cache.c b/libdw/frame-cache.c
index 6c89858a..6f6f777e 100644
--- a/libdw/frame-cache.c
+++ b/libdw/frame-cache.c
@@ -64,6 +64,7 @@ __libdw_destroy_frame_cache (Dwarf_CFI *cache)
   eu_search_tree_fini (&cache->fde_tree, free_fde);
   eu_search_tree_fini (&cache->cie_tree, free_cie);
   eu_search_tree_fini (&cache->expr_tree, free_expr);
+  mutex_fini (cache->lock);
 
   if (cache->ebl != NULL && cache->ebl != (void *) -1l)
     ebl_closebackend (cache->ebl);
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index de80cd4e..25d53d31 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -269,7 +269,7 @@ struct Dwarf
      __libdw_intern_next_unit.  */
   mutex_define(, dwarf_lock);
 
-  /* Synchronize access to dwarf_macro_getsrcfiles.  */
+  /* Synchronize access to dwarf_macro_getsrcfiles and cache_op_table.  */
   mutex_define(, macro_lock);
 
   /* Internal memory handling.  This is basically a simplified thread-local
@@ -471,6 +471,10 @@ struct Dwarf_CU
      Covers __libdw_str_offsets_base_off.  */
   mutex_define(, str_off_base_lock);
 
+  /* Synchronize access to is_constant_offset.  Should also be held
+     when calling __libdw_intern_expression with Dwarf_CU members.  */
+  mutex_define(, intern_lock);
+
   /* Memory boundaries of this CU.  */
   void *startp;
   void *endp;
@@ -949,8 +953,9 @@ extern int __libdw_visit_scopes (unsigned int depth,
 				 void *arg)
   __nonnull_attribute__ (2, 4) internal_function;
 
-/* Parse a DWARF Dwarf_Block into an array of Dwarf_Op's,
-   and cache the result (via tsearch).  */
+/* Parse a DWARF Dwarf_Block into an array of Dwarf_Op's, and cache the
+   result (via tsearch).  The owner of CACHE (typically a Dwarf_CU or
+   Dwarf_CFI_s) must hold a lock when calling this function.  */
 extern int __libdw_intern_expression (Dwarf *dbg,
 				      bool other_byte_order,
 				      unsigned int address_size,
diff --git a/libdw/libdw_findcu.c b/libdw/libdw_findcu.c
index 0e4dcc37..21c8ed0e 100644
--- a/libdw/libdw_findcu.c
+++ b/libdw/libdw_findcu.c
@@ -181,6 +181,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
   rwlock_init (newp->split_lock);
   mutex_init (newp->src_lock);
   mutex_init (newp->str_off_base_lock);
+  mutex_init (newp->intern_lock);
 
   /* v4 debug type units have version == 4 and unit_type == DW_UT_type.  */
   if (debug_types)
@@ -240,8 +241,6 @@ struct Dwarf_CU *
 internal_function
 __libdw_findcu (Dwarf *dbg, Dwarf_Off start, bool v4_debug_types)
 {
-  mutex_lock (dbg->dwarf_lock);
-
   search_tree *tree = v4_debug_types ? &dbg->tu_tree : &dbg->cu_tree;
   Dwarf_Off *next_offset
     = v4_debug_types ? &dbg->next_tu_offset : &dbg->next_cu_offset;
@@ -250,6 +249,12 @@ __libdw_findcu (Dwarf *dbg, Dwarf_Off start, bool v4_debug_types)
   struct Dwarf_CU fake = { .start = start, .end = 0 };
   struct Dwarf_CU **found = eu_tfind (&fake, tree, findcu_cb);
   struct Dwarf_CU *result = NULL;
+  if (found != NULL)
+    return *found;
+
+  mutex_lock (dbg->dwarf_lock);
+
+  found = eu_tfind_nolock (&fake, tree, findcu_cb);
   if (found != NULL)
     {
       mutex_unlock (dbg->dwarf_lock);