Implement LB policy updates

7 files changed, 80 insertions, 19 deletions

diff --git a/src/core/lib/channel/channel_args.c b/src/core/lib/channel/channel_args.c
index 247b134938..2df07c8ae6 100644
--- a/src/core/lib/channel/channel_args.c
+++ b/src/core/lib/channel/channel_args.c
@@ -129,9 +129,23 @@ grpc_channel_args *grpc_channel_args_copy(const grpc_channel_args *src) {
   return grpc_channel_args_copy_and_add(src, NULL, 0);
 }
 
-grpc_channel_args *grpc_channel_args_merge(const grpc_channel_args *a,
+grpc_channel_args *grpc_channel_args_union(const grpc_channel_args *a,
                                            const grpc_channel_args *b) {
-  return grpc_channel_args_copy_and_add(a, b->args, b->num_args);
+  const size_t max_out = (a->num_args + b->num_args);
+  grpc_arg *uniques = gpr_malloc(sizeof(*uniques) * max_out);
+  for (size_t i = 0; i < a->num_args; ++i) uniques[i] = a->args[i];
+
+  size_t uniques_idx = a->num_args;
+  for (size_t i = 0; i < b->num_args; ++i) {
+    const char *b_key = b->args[i].key;
+    if (grpc_channel_args_find(a, b_key) == NULL) {  // not found
+      uniques[uniques_idx++] = b->args[i];
+    }
+  }
+  grpc_channel_args *result =
+      grpc_channel_args_copy_and_add(NULL, uniques, uniques_idx);
+  gpr_free(uniques);
+  return result;
 }
 
 static int cmp_arg(const grpc_arg *a, const grpc_arg *b) {
diff --git a/src/core/lib/channel/channel_args.h b/src/core/lib/channel/channel_args.h
index f0f603e251..128afd00d4 100644
--- a/src/core/lib/channel/channel_args.h
+++ b/src/core/lib/channel/channel_args.h
@@ -63,8 +63,8 @@ grpc_channel_args *grpc_channel_args_copy_and_add_and_remove(
     const grpc_channel_args *src, const char **to_remove, size_t num_to_remove,
     const grpc_arg *to_add, size_t num_to_add);
 
-/** Concatenate args from \a a and \a b into a new instance */
-grpc_channel_args *grpc_channel_args_merge(const grpc_channel_args *a,
+/** Perform the union of \a a and \a b, prioritizing \a a entries */
+grpc_channel_args *grpc_channel_args_union(const grpc_channel_args *a,
                                            const grpc_channel_args *b);
 
 /** Destroy arguments created by \a grpc_channel_args_copy */
diff --git a/src/core/lib/iomgr/polling_entity.h b/src/core/lib/iomgr/polling_entity.h
index e81531053c..740e553b2a 100644
--- a/src/core/lib/iomgr/polling_entity.h
+++ b/src/core/lib/iomgr/polling_entity.h
@@ -38,9 +38,8 @@
 #include "src/core/lib/iomgr/pollset_set.h"
 
 /* A grpc_polling_entity is a pollset-or-pollset_set container. It allows
- * functions that
- * accept a pollset XOR a pollset_set to do so through an abstract interface.
- * No ownership is taken. */
+ * functions that accept a pollset XOR a pollset_set to do so through an
+ * abstract interface. No ownership is taken. */
 
 typedef struct grpc_polling_entity {
   union {
@@ -64,18 +63,14 @@ grpc_pollset_set *grpc_polling_entity_pollset_set(grpc_polling_entity *pollent);
 bool grpc_polling_entity_is_empty(const grpc_polling_entity *pollent);
 
 /** Add the pollset or pollset_set in \a pollent to the destination pollset_set
- * \a
- * pss_dst */
+ * \a * pss_dst */
 void grpc_polling_entity_add_to_pollset_set(grpc_exec_ctx *exec_ctx,
                                             grpc_polling_entity *pollent,
                                             grpc_pollset_set *pss_dst);
 
 /** Delete the pollset or pollset_set in \a pollent from the destination
- * pollset_set \a
- * pss_dst */
+ * pollset_set \a * pss_dst */
 void grpc_polling_entity_del_from_pollset_set(grpc_exec_ctx *exec_ctx,
                                               grpc_polling_entity *pollent,
                                               grpc_pollset_set *pss_dst);
-/* pollset_set specific */
-
 #endif /* GRPC_CORE_LIB_IOMGR_POLLING_ENTITY_H */
diff --git a/src/core/lib/security/transport/lb_targets_info.c b/src/core/lib/security/transport/lb_targets_info.c
index e73483c039..8bb06b1f61 100644
--- a/src/core/lib/security/transport/lb_targets_info.c
+++ b/src/core/lib/security/transport/lb_targets_info.c
@@ -44,7 +44,9 @@ static void *targets_info_copy(void *p) { return grpc_slice_hash_table_ref(p); }
 static void targets_info_destroy(grpc_exec_ctx *exec_ctx, void *p) {
   grpc_slice_hash_table_unref(exec_ctx, p);
 }
-static int targets_info_cmp(void *a, void *b) { return GPR_ICMP(a, b); }
+static int targets_info_cmp(void *a, void *b) {
+  return grpc_slice_hash_table_cmp(a, b);
+}
 static const grpc_arg_pointer_vtable server_to_balancer_names_vtable = {
     targets_info_copy, targets_info_destroy, targets_info_cmp};
 
diff --git a/src/core/lib/slice/slice_hash_table.c b/src/core/lib/slice/slice_hash_table.c
index 444f22aa19..2d9ff61c95 100644
--- a/src/core/lib/slice/slice_hash_table.c
+++ b/src/core/lib/slice/slice_hash_table.c
@@ -43,6 +43,7 @@
 struct grpc_slice_hash_table {
   gpr_refcount refs;
   void (*destroy_value)(grpc_exec_ctx* exec_ctx, void* value);
+  int (*value_cmp)(void* a, void* b);
   size_t size;
   size_t max_num_probes;
   grpc_slice_hash_table_entry* entries;
@@ -72,10 +73,12 @@ static void grpc_slice_hash_table_add(grpc_slice_hash_table* table,
 
 grpc_slice_hash_table* grpc_slice_hash_table_create(
     size_t num_entries, grpc_slice_hash_table_entry* entries,
-    void (*destroy_value)(grpc_exec_ctx* exec_ctx, void* value)) {
+    void (*destroy_value)(grpc_exec_ctx* exec_ctx, void* value),
+    int (*value_cmp)(void* a, void* b)) {
   grpc_slice_hash_table* table = gpr_zalloc(sizeof(*table));
   gpr_ref_init(&table->refs, 1);
   table->destroy_value = destroy_value;
+  table->value_cmp = value_cmp;
   // Keep load factor low to improve performance of lookups.
   table->size = num_entries * 2;
   const size_t entry_size = sizeof(grpc_slice_hash_table_entry) * table->size;
@@ -121,3 +124,37 @@ void* grpc_slice_hash_table_get(const grpc_slice_hash_table* table,
   }
   return NULL;  // Not found.
 }
+
+static int pointer_cmp(void* a, void* b) { return GPR_ICMP(a, b); }
+int grpc_slice_hash_table_cmp(const grpc_slice_hash_table* a,
+                              const grpc_slice_hash_table* b) {
+  int (*const value_cmp_fn_a)(void* a, void* b) =
+      a->value_cmp != NULL ? a->value_cmp : pointer_cmp;
+  int (*const value_cmp_fn_b)(void* a, void* b) =
+      b->value_cmp != NULL ? b->value_cmp : pointer_cmp;
+  // Compare value_fns
+  const int value_fns_cmp =
+      GPR_ICMP((void*)value_cmp_fn_a, (void*)value_cmp_fn_b);
+  if (value_fns_cmp != 0) return value_fns_cmp;
+  // Compare sizes
+  if (a->size < b->size) return -1;
+  if (a->size > b->size) return 1;
+  // Compare rows.
+  for (size_t i = 0; i < a->size; ++i) {
+    if (is_empty(&a->entries[i])) {
+      if (!is_empty(&b->entries[i])) {
+        return -1;  // a empty but b non-empty
+      }
+      continue;  // both empty, no need to check key or value
+    } else if (is_empty(&b->entries[i])) {
+      return 1;  // a non-empty but b empty
+    }
+    // neither entry is empty
+    const int key_cmp = grpc_slice_cmp(a->entries[i].key, b->entries[i].key);
+    if (key_cmp != 0) return key_cmp;
+    const int value_cmp =
+        value_cmp_fn_a(a->entries[i].value, b->entries[i].value);
+    if (value_cmp != 0) return value_cmp;
+  }
+  return 0;
+}
diff --git a/src/core/lib/slice/slice_hash_table.h b/src/core/lib/slice/slice_hash_table.h
index 1e61c5eb11..07988abff4 100644
--- a/src/core/lib/slice/slice_hash_table.h
+++ b/src/core/lib/slice/slice_hash_table.h
@@ -54,11 +54,15 @@ typedef struct grpc_slice_hash_table_entry {
 } grpc_slice_hash_table_entry;
 
 /** Creates a new hash table of containing \a entries, which is an array
-    of length \a num_entries.  Takes ownership of all keys and values in
-    \a entries.  Values will be cleaned up via \a destroy_value(). */
+    of length \a num_entries.  Takes ownership of all keys and values in \a
+    entries.  Values will be cleaned up via \a destroy_value(). If not NULL, \a
+    value_cmp will be used to compare values in the context of \a
+    grpc_slice_hash_table_cmp. If NULL, raw pointer (\a GPR_ICMP) comparison
+    will be used. */
 grpc_slice_hash_table *grpc_slice_hash_table_create(
     size_t num_entries, grpc_slice_hash_table_entry *entries,
-    void (*destroy_value)(grpc_exec_ctx *exec_ctx, void *value));
+    void (*destroy_value)(grpc_exec_ctx *exec_ctx, void *value),
+    int (*value_cmp)(void *a, void *b));
 
 grpc_slice_hash_table *grpc_slice_hash_table_ref(grpc_slice_hash_table *table);
 void grpc_slice_hash_table_unref(grpc_exec_ctx *exec_ctx,
@@ -69,4 +73,13 @@ void grpc_slice_hash_table_unref(grpc_exec_ctx *exec_ctx,
 void *grpc_slice_hash_table_get(const grpc_slice_hash_table *table,
                                 const grpc_slice key);
 
+/** Compares \a a vs. \a b.
+ * A table is considered "smaller" (resp. "greater") if:
+ *  - GPR_ICMP(a->value_cmp, b->value_cmp) < 1 (resp. > 1),
+ *  - else, it contains fewer (resp. more) entries,
+ *  - else, if strcmp(a_key, b_key) < 1 (resp. > 1),
+ *  - else, if value_cmp(a_value, b_value) < 1 (resp. > 1). */
+int grpc_slice_hash_table_cmp(const grpc_slice_hash_table *a,
+                              const grpc_slice_hash_table *b);
+
 #endif /* GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H */
diff --git a/src/core/lib/transport/service_config.c b/src/core/lib/transport/service_config.c
index 6aecb7fa93..107818f4d1 100644
--- a/src/core/lib/transport/service_config.c
+++ b/src/core/lib/transport/service_config.c
@@ -229,7 +229,7 @@ grpc_slice_hash_table* grpc_service_config_create_method_config_table(
   grpc_slice_hash_table* method_config_table = NULL;
   if (entries != NULL) {
     method_config_table =
-        grpc_slice_hash_table_create(num_entries, entries, destroy_value);
+        grpc_slice_hash_table_create(num_entries, entries, destroy_value, NULL);
     gpr_free(entries);
   }
   return method_config_table;