diff --git a/libselinux/src/label_file.c b/libselinux/src/label_file.c
index f84d470b..560d8c3d 100644
--- a/libselinux/src/label_file.c
+++ b/libselinux/src/label_file.c
@@ -389,10 +389,12 @@ end_arch_check:
 			spec->prefix_len = prefix_len;
 		}
 
-		rc = regex_load_mmap(mmap_area, &spec->regex, reg_arch_matches);
+		rc = regex_load_mmap(mmap_area, &spec->regex, reg_arch_matches,
+				     &spec->regex_compiled);
 		if (rc < 0)
 			goto out;
 
+		__pthread_mutex_init(&spec->regex_lock, NULL);
 		data->nspec++;
 	}
 
@@ -810,6 +812,7 @@ static void closef(struct selabel_handle *rec)
 		free(spec->lr.ctx_trans);
 		free(spec->lr.ctx_raw);
 		regex_data_free(spec->regex);
+		__pthread_mutex_destroy(&spec->regex_lock);
 		if (spec->from_mmap)
 			continue;
 		free(spec->regex_str);
diff --git a/libselinux/src/label_file.h b/libselinux/src/label_file.h
index de804aed..aa576d8e 100644
--- a/libselinux/src/label_file.h
+++ b/libselinux/src/label_file.h
@@ -2,6 +2,7 @@
 #define _SELABEL_FILE_H_
 
 #include <errno.h>
+#include <pthread.h>
 #include <string.h>
 
 #include <sys/stat.h>
@@ -16,6 +17,7 @@
 
 #include "callbacks.h"
 #include "label_internal.h"
+#include "selinux_internal.h"
 
 #define SELINUX_MAGIC_COMPILED_FCONTEXT	0xf97cff8a
 
@@ -42,6 +44,8 @@ struct spec {
 	char *regex_str;	/* regular expession string for diagnostics */
 	char *type_str;		/* type string for diagnostic messages */
 	struct regex_data * regex; /* backend dependent regular expression data */
+	bool regex_compiled; /* bool to indicate if the regex is compiled */
+	pthread_mutex_t regex_lock; /* lock for lazy compilation of regex */
 	mode_t mode;		/* mode format value */
 	int matches;		/* number of matching pathnames */
 	int stem_id;		/* indicates which stem-compression item */
@@ -339,9 +343,27 @@ static inline int compile_regex(struct saved_data *data, struct spec *spec,
 	struct stem *stem_arr = data->stem_arr;
 	size_t len;
 	int rc;
-
-	if (spec->regex)
+	bool regex_compiled;
+
+	/* We really want pthread_once() here, but since its
+	 * init_routine does not take a parameter, it's not possible
+	 * to use, so we generate the same effect with atomics and a
+	 * mutex */
+	regex_compiled =
+		__atomic_load_n(&spec->regex_compiled, __ATOMIC_ACQUIRE);
+	if (regex_compiled) {
 		return 0; /* already done */
+	}
+
+	__pthread_mutex_lock(&spec->regex_lock);
+	/* Check if another thread compiled the regex while we waited
+	 * on the mutex */
+	regex_compiled =
+		__atomic_load_n(&spec->regex_compiled, __ATOMIC_ACQUIRE);
+	if (regex_compiled) {
+		__pthread_mutex_unlock(&spec->regex_lock);
+		return 0;
+	}
 
 	/* Skip the fixed stem. */
 	reg_buf = spec->regex_str;
@@ -354,6 +376,7 @@ static inline int compile_regex(struct saved_data *data, struct spec *spec,
 	if (!anchored_regex) {
 		if (errbuf)
 			*errbuf = "out of memory";
+		__pthread_mutex_unlock(&spec->regex_lock);
 		return -1;
 	}
 
@@ -374,10 +397,13 @@ static inline int compile_regex(struct saved_data *data, struct spec *spec,
 					sizeof(regex_error_format_buffer));
 			*errbuf = &regex_error_format_buffer[0];
 		}
+		__pthread_mutex_unlock(&spec->regex_lock);
 		return -1;
 	}
 
 	/* Done. */
+	__atomic_store_n(&spec->regex_compiled, true, __ATOMIC_RELEASE);
+	__pthread_mutex_unlock(&spec->regex_lock);
 	return 0;
 }
 
@@ -439,6 +465,8 @@ static inline int process_line(struct selabel_handle *rec,
 	/* process and store the specification in spec. */
 	spec_arr[nspec].stem_id = find_stem_from_spec(data, regex);
 	spec_arr[nspec].regex_str = regex;
+	__pthread_mutex_init(&spec_arr[nspec].regex_lock, NULL);
+	spec_arr[nspec].regex_compiled = false;
 
 	spec_arr[nspec].type_str = type;
 	spec_arr[nspec].mode = 0;
diff --git a/libselinux/src/regex.c b/libselinux/src/regex.c
index ec1b0c4a..dfc15d63 100644
--- a/libselinux/src/regex.c
+++ b/libselinux/src/regex.c
@@ -1,10 +1,12 @@
 #include <assert.h>
+#include <pthread.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <string.h>
 
 #include "regex.h"
 #include "label_file.h"
+#include "selinux_internal.h"
 
 #ifdef USE_PCRE2
 #define REGEX_ARCH_SIZE_T PCRE2_SIZE
@@ -63,6 +65,7 @@ struct regex_data {
 	 * pattern in pcre2
 	 */
 	pcre2_match_data *match_data;
+	pthread_mutex_t match_mutex;
 };
 
 int regex_prepare_data(struct regex_data **regex, char const *pattern_string,
@@ -106,11 +109,12 @@ char const *regex_version(void)
 }
 
 int regex_load_mmap(struct mmap_area *mmap_area, struct regex_data **regex,
-		    int do_load_precompregex)
+		    int do_load_precompregex, bool *regex_compiled)
 {
 	int rc;
 	uint32_t entry_len;
 
+	*regex_compiled = false;
 	rc = next_entry(&entry_len, mmap_area, sizeof(uint32_t));
 	if (rc < 0)
 		return -1;
@@ -138,6 +142,8 @@ int regex_load_mmap(struct mmap_area *mmap_area, struct regex_data **regex,
 		    pcre2_match_data_create_from_pattern((*regex)->regex, NULL);
 		if (!(*regex)->match_data)
 			goto err;
+
+		*regex_compiled = true;
 	}
 
 	/* and skip the decoded bit */
@@ -199,6 +205,7 @@ void regex_data_free(struct regex_data *regex)
 			pcre2_code_free(regex->regex);
 		if (regex->match_data)
 			pcre2_match_data_free(regex->match_data);
+		__pthread_mutex_destroy(&regex->match_mutex);
 		free(regex);
 	}
 }
@@ -206,9 +213,11 @@ void regex_data_free(struct regex_data *regex)
 int regex_match(struct regex_data *regex, char const *subject, int partial)
 {
 	int rc;
+	__pthread_mutex_lock(&regex->match_mutex);
 	rc = pcre2_match(
 	    regex->regex, (PCRE2_SPTR)subject, PCRE2_ZERO_TERMINATED, 0,
 	    partial ? PCRE2_PARTIAL_SOFT : 0, regex->match_data, NULL);
+	__pthread_mutex_unlock(&regex->match_mutex);
 	if (rc > 0)
 		return REGEX_MATCH;
 	switch (rc) {
@@ -244,6 +253,14 @@ int regex_cmp(struct regex_data *regex1, struct regex_data *regex2)
 	return SELABEL_EQUAL;
 }
 
+struct regex_data *regex_data_create(void)
+{
+	struct regex_data *regex_data =
+		(struct regex_data *)calloc(1, sizeof(struct regex_data));
+	__pthread_mutex_init(&regex_data->match_mutex, NULL);
+	return regex_data;
+}
+
 #else // !USE_PCRE2
 char const *regex_arch_string(void)
 {
@@ -302,7 +319,7 @@ char const *regex_version(void)
 }
 
 int regex_load_mmap(struct mmap_area *mmap_area, struct regex_data **regex,
-		    int unused __attribute__((unused)))
+		    int unused __attribute__((unused)), bool *regex_compiled)
 {
 	int rc;
 	uint32_t entry_len;
@@ -347,6 +364,8 @@ int regex_load_mmap(struct mmap_area *mmap_area, struct regex_data **regex,
 		if (rc < 0 || info_len != entry_len)
 			goto err;
 	}
+
+	*regex_compiled = true;
 	return 0;
 
 err:
@@ -472,13 +491,13 @@ int regex_cmp(struct regex_data *regex1, struct regex_data *regex2)
 	return SELABEL_EQUAL;
 }
 
-#endif
-
 struct regex_data *regex_data_create(void)
 {
 	return (struct regex_data *)calloc(1, sizeof(struct regex_data));
 }
 
+#endif
+
 void regex_format_error(struct regex_error_data const *error_data, char *buffer,
 			size_t buf_size)
 {
diff --git a/libselinux/src/regex.h b/libselinux/src/regex.h
index 186c5ecc..eb8ca501 100644
--- a/libselinux/src/regex.h
+++ b/libselinux/src/regex.h
@@ -1,6 +1,7 @@
 #ifndef SRC_REGEX_H_
 #define SRC_REGEX_H_
 
+#include <stdbool.h>
 #include <stdio.h>
 
 #ifdef USE_PCRE2
@@ -98,13 +99,17 @@ int regex_prepare_data(struct regex_data **regex, char const *pattern_string,
  *            with regex_data_create and must be freed with regex_data_free.
  * @arg do_load_precompregex If non-zero precompiled patterns get loaded from
  *			     the mmap region (ignored by PCRE1 back-end).
+ * @arg regex_compiled Set to true if a precompiled pattern was loaded
+ * 		       into regex, otherwise set to false to indicate later
+ *		       compilation must occur
  *
  * @retval 0 on success
  * @retval -1 on error
  */
 int regex_load_mmap(struct mmap_area *map_area,
 		    struct regex_data **regex,
-		    int do_load_precompregex) hidden;
+		    int do_load_precompregex,
+		    bool *regex_compiled) hidden;
 /**
  * This function stores a precompiled regular expression to a file.
  * In the case of PCRE, it just dumps the binary representation of the
diff --git a/libselinux/src/selinux_internal.h b/libselinux/src/selinux_internal.h
index 54949c13..dfc421cc 100644
--- a/libselinux/src/selinux_internal.h
+++ b/libselinux/src/selinux_internal.h
@@ -144,6 +144,38 @@ extern int selinux_page_size hidden;
 			pthread_setspecific(KEY, VALUE);	\
 	} while (0)
 
+/* selabel_lookup() is only thread safe if we're compiled with pthreads */
+
+#pragma weak pthread_mutex_init
+#pragma weak pthread_mutex_destroy
+#pragma weak pthread_mutex_lock
+#pragma weak pthread_mutex_unlock
+
+#define __pthread_mutex_init(LOCK, ATTR) 			\
+	do {							\
+		if (pthread_mutex_init != NULL)			\
+			pthread_mutex_init(LOCK, ATTR);		\
+	} while (0)
+
+#define __pthread_mutex_destroy(LOCK) 				\
+	do {							\
+		if (pthread_mutex_destroy != NULL)		\
+			pthread_mutex_destroy(LOCK);		\
+	} while (0)
+
+#define __pthread_mutex_lock(LOCK) 				\
+	do {							\
+		if (pthread_mutex_lock != NULL)			\
+			pthread_mutex_lock(LOCK);		\
+	} while (0)
+
+#define __pthread_mutex_unlock(LOCK) 				\
+	do {							\
+		if (pthread_mutex_unlock != NULL)		\
+			pthread_mutex_unlock(LOCK);		\
+	} while (0)
+
+
 #define SELINUXDIR "/etc/selinux/"
 #define SELINUXCONFIG SELINUXDIR "config"
 
