diff --git a/lib/conntrack-private.h b/lib/conntrack-private.h
index d9461b811..34c688821 100644
--- a/lib/conntrack-private.h
+++ b/lib/conntrack-private.h
@@ -193,7 +193,7 @@ struct conntrack {
     struct cmap conns OVS_GUARDED;
     struct ovs_list exp_lists[N_CT_TM] OVS_GUARDED;
     struct cmap zone_limits OVS_GUARDED;
-    struct hmap timeout_policies OVS_GUARDED;
+    struct cmap timeout_policies OVS_GUARDED;
     uint32_t hash_basis; /* Salt for hashing a connection key. */
     pthread_t clean_thread; /* Periodically cleans up connection tracker. */
     struct latch clean_thread_exit; /* To destroy the 'clean_thread'. */
diff --git a/lib/conntrack-tp.c b/lib/conntrack-tp.c
index a586d3a8d..c2245038b 100644
--- a/lib/conntrack-tp.c
+++ b/lib/conntrack-tp.c
@@ -47,14 +47,15 @@ static unsigned int ct_dpif_netdev_tp_def[] = {
 };
 
 static struct timeout_policy *
-timeout_policy_lookup(struct conntrack *ct, int32_t tp_id)
+timeout_policy_lookup_protected(struct conntrack *ct, int32_t tp_id)
     OVS_REQUIRES(ct->ct_lock)
 {
     struct timeout_policy *tp;
     uint32_t hash;
 
     hash = hash_int(tp_id, ct->hash_basis);
-    HMAP_FOR_EACH_IN_BUCKET (tp, node, hash, &ct->timeout_policies) {
+    CMAP_FOR_EACH_WITH_HASH_PROTECTED (tp, node, hash,
+                                       &ct->timeout_policies) {
         if (tp->policy.id == tp_id) {
             return tp;
         }
@@ -62,20 +63,25 @@ timeout_policy_lookup(struct conntrack *ct, int32_t tp_id)
     return NULL;
 }
 
-struct timeout_policy *
-timeout_policy_get(struct conntrack *ct, int32_t tp_id)
+static struct timeout_policy *
+timeout_policy_lookup(struct conntrack *ct, int32_t tp_id)
 {
     struct timeout_policy *tp;
+    uint32_t hash;
 
-    ovs_mutex_lock(&ct->ct_lock);
-    tp = timeout_policy_lookup(ct, tp_id);
-    if (!tp) {
-        ovs_mutex_unlock(&ct->ct_lock);
-        return NULL;
+    hash = hash_int(tp_id, ct->hash_basis);
+    CMAP_FOR_EACH_WITH_HASH (tp, node, hash, &ct->timeout_policies) {
+        if (tp->policy.id == tp_id) {
+            return tp;
+        }
     }
+    return NULL;
+}
 
-    ovs_mutex_unlock(&ct->ct_lock);
-    return tp;
+struct timeout_policy *
+timeout_policy_get(struct conntrack *ct, int32_t tp_id)
+{
+    return timeout_policy_lookup(ct, tp_id);
 }
 
 static void
@@ -125,27 +131,30 @@ timeout_policy_create(struct conntrack *ct,
     init_default_tp(tp, tp_id);
     update_existing_tp(tp, new_tp);
     hash = hash_int(tp_id, ct->hash_basis);
-    hmap_insert(&ct->timeout_policies, &tp->node, hash);
+    cmap_insert(&ct->timeout_policies, &tp->node, hash);
 }
 
 static void
 timeout_policy_clean(struct conntrack *ct, struct timeout_policy *tp)
     OVS_REQUIRES(ct->ct_lock)
 {
-    hmap_remove(&ct->timeout_policies, &tp->node);
-    free(tp);
+    uint32_t hash = hash_int(tp->policy.id, ct->hash_basis);
+    cmap_remove(&ct->timeout_policies, &tp->node, hash);
+    ovsrcu_postpone(free, tp);
 }
 
 static int
-timeout_policy_delete__(struct conntrack *ct, uint32_t tp_id)
+timeout_policy_delete__(struct conntrack *ct, uint32_t tp_id,
+                        bool warn_on_error)
     OVS_REQUIRES(ct->ct_lock)
 {
+    struct timeout_policy *tp;
     int err = 0;
-    struct timeout_policy *tp = timeout_policy_lookup(ct, tp_id);
 
+    tp = timeout_policy_lookup_protected(ct, tp_id);
     if (tp) {
         timeout_policy_clean(ct, tp);
-    } else {
+    } else if (warn_on_error) {
         VLOG_WARN_RL(&rl, "Failed to delete a non-existent timeout "
                      "policy: id=%d", tp_id);
         err = ENOENT;
@@ -159,7 +168,7 @@ timeout_policy_delete(struct conntrack *ct, uint32_t tp_id)
     int err;
 
     ovs_mutex_lock(&ct->ct_lock);
-    err = timeout_policy_delete__(ct, tp_id);
+    err = timeout_policy_delete__(ct, tp_id, true);
     ovs_mutex_unlock(&ct->ct_lock);
     return err;
 }
@@ -170,7 +179,7 @@ timeout_policy_init(struct conntrack *ct)
 {
     struct timeout_policy tp;
 
-    hmap_init(&ct->timeout_policies);
+    cmap_init(&ct->timeout_policies);
 
     /* Create default timeout policy. */
     memset(&tp, 0, sizeof tp);
@@ -182,14 +191,11 @@ int
 timeout_policy_update(struct conntrack *ct,
                       struct timeout_policy *new_tp)
 {
-    int err = 0;
     uint32_t tp_id = new_tp->policy.id;
+    int err = 0;
 
     ovs_mutex_lock(&ct->ct_lock);
-    struct timeout_policy *tp = timeout_policy_lookup(ct, tp_id);
-    if (tp) {
-        err = timeout_policy_delete__(ct, tp_id);
-    }
+    timeout_policy_delete__(ct, tp_id, false);
     timeout_policy_create(ct, new_tp);
     ovs_mutex_unlock(&ct->ct_lock);
     return err;
diff --git a/lib/conntrack.c b/lib/conntrack.c
index 6df1142b9..38ddc9b91 100644
--- a/lib/conntrack.c
+++ b/lib/conntrack.c
@@ -542,10 +542,13 @@ conntrack_destroy(struct conntrack *ct)
     cmap_destroy(&ct->zone_limits);
 
     struct timeout_policy *tp;
-    HMAP_FOR_EACH_POP (tp, node, &ct->timeout_policies) {
-        free(tp);
+    CMAP_FOR_EACH (tp, node, &ct->timeout_policies) {
+        uint32_t hash = hash_int(tp->policy.id, ct->hash_basis);
+
+        cmap_remove(&ct->timeout_policies, &tp->node, hash);
+        ovsrcu_postpone(free, tp);
     }
-    hmap_destroy(&ct->timeout_policies);
+    cmap_destroy(&ct->timeout_policies);
 
     ovs_mutex_unlock(&ct->ct_lock);
     ovs_mutex_destroy(&ct->ct_lock);
diff --git a/lib/conntrack.h b/lib/conntrack.h
index 58b181834..b064abc9f 100644
--- a/lib/conntrack.h
+++ b/lib/conntrack.h
@@ -113,7 +113,7 @@ struct conntrack_zone_limit {
 };
 
 struct timeout_policy {
-    struct hmap_node node;
+    struct cmap_node node;
     struct ct_dpif_timeout_policy policy;
 };
 
