X-Git-Url: https://git.lttng.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=20d389d38517d786477e4acff9f8a87fe5b6b1ae;hp=6bc25aed32e09817bcf74280c19bc0022789551c;hb=3967a8a8984fe5cb7ac83996db6709c8aae857c2;hpb=df44348d52532adf7b7a28edc5fdf5b43255c36b

diff --git a/rculfhash.c b/rculfhash.c
index 6bc25ae..20d389d 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -119,11 +119,15 @@
 #define dbg_printf(fmt, args...)
 #endif
 
-#define CHAIN_LEN_TARGET		4
-#define CHAIN_LEN_RESIZE_THRESHOLD	8
-
-/* Commit counter changes to global counter each 1024 steps */
+/*
+ * Per-CPU split-counters lazily update the global counter each 1024
+ * addition/removal. It automatically keeps track of resize required.
+ * We use the bucket length as indicator for need to expand for small
+ * tables and machines lacking per-cpu data suppport.
+ */
 #define COUNT_COMMIT_ORDER		10
+#define CHAIN_LEN_TARGET		1
+#define CHAIN_LEN_RESIZE_THRESHOLD	3
 
 #ifndef max
 #define max(a, b)	((a) > (b) ? (a) : (b))
@@ -139,7 +143,7 @@
 #define FLAGS_MASK		((1UL << 2) - 1)
 
 struct ht_items_count {
-	unsigned long v;
+	unsigned long add, remove;
 } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
 
 struct rcu_table {
@@ -369,9 +373,12 @@ void cds_lfht_resize_lazy(struct cds_lfht *ht, struct rcu_table *t, int growth);
  * In the unfortunate event the number of CPUs reported would be
  * inaccurate, we use modulo arithmetic on the number of CPUs we got.
  */
-
 #if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF)
 
+static
+void cds_lfht_resize_lazy_count(struct cds_lfht *ht, struct rcu_table *t,
+				unsigned long count);
+
 static long nr_cpus_mask = -1;
 
 static
@@ -424,24 +431,17 @@ int ht_get_cpu(void)
 }
 
 static
-unsigned long ht_count_update(struct cds_lfht *ht, unsigned int value)
+void ht_count_add(struct cds_lfht *ht, struct rcu_table *t)
 {
+	unsigned long percpu_count;
 	int cpu;
 
 	if (unlikely(!ht->percpu_count))
-		return 0;
+		return;
 	cpu = ht_get_cpu();
 	if (unlikely(cpu < 0))
-		return 0;
-	return uatomic_add_return(&ht->percpu_count[cpu].v, 1);
-}
-
-static
-void ht_count_add(struct cds_lfht *ht, struct rcu_table *t)
-{
-	unsigned long percpu_count;
-
-	percpu_count = ht_count_update(ht, 1);
+		return;
+	percpu_count = uatomic_add_return(&ht->percpu_count[cpu].add, 1);
 	if (unlikely(!(percpu_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))) {
 		unsigned long count;
 
@@ -450,8 +450,12 @@ void ht_count_add(struct cds_lfht *ht, struct rcu_table *t)
 					   1UL << COUNT_COMMIT_ORDER);
 		/* If power of 2 */
 		if (!(count & (count - 1))) {
-			dbg_printf("add global %lu\n", count);
-			cds_lfht_resize_lazy(ht, t, 1);
+			if ((count >> CHAIN_LEN_RESIZE_THRESHOLD)
+					< t->size)
+				return;
+			dbg_printf("add set global %lu\n", count);
+			cds_lfht_resize_lazy_count(ht, t,
+				count >> (CHAIN_LEN_TARGET - 1));
 		}
 	}
 }
@@ -460,18 +464,28 @@ static
 void ht_count_remove(struct cds_lfht *ht, struct rcu_table *t)
 {
 	unsigned long percpu_count;
+	int cpu;
 
-	percpu_count = ht_count_update(ht, -1);
+	if (unlikely(!ht->percpu_count))
+		return;
+	cpu = ht_get_cpu();
+	if (unlikely(cpu < 0))
+		return;
+	percpu_count = uatomic_add_return(&ht->percpu_count[cpu].remove, -1);
 	if (unlikely(!(percpu_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))) {
 		unsigned long count;
 
 		dbg_printf("remove percpu %lu\n", percpu_count);
 		count = uatomic_add_return(&ht->count,
-					   1UL << COUNT_COMMIT_ORDER);
+					   -(1UL << COUNT_COMMIT_ORDER));
 		/* If power of 2 */
 		if (!(count & (count - 1))) {
-			dbg_printf("remove global %lu\n", count);
-			cds_lfht_resize_lazy(ht, t, -1);
+			if ((count >> CHAIN_LEN_RESIZE_THRESHOLD)
+					>= t->size)
+				return;
+			dbg_printf("remove set global %lu\n", count);
+			cds_lfht_resize_lazy_count(ht, t,
+				count >> (CHAIN_LEN_TARGET - 1));
 		}
 	}
 }
@@ -492,12 +506,12 @@ void free_per_cpu_items_count(struct ht_items_count *count)
 }
 
 static
-void ht_count_add(struct cds_lfht *ht)
+void ht_count_add(struct cds_lfht *ht, struct rcu_table *t)
 {
 }
 
 static
-void ht_count_remove(struct cds_lfht *ht)
+void ht_count_remove(struct cds_lfht *ht, struct rcu_table *t)
 {
 }
 
@@ -508,7 +522,15 @@ static
 void check_resize(struct cds_lfht *ht, struct rcu_table *t,
 		  uint32_t chain_len)
 {
-	return; 	//TEST
+	unsigned long count;
+
+	count = uatomic_read(&ht->count);
+	/*
+	 * Use bucket-local length for small table expand and for
+	 * environments lacking per-cpu data support.
+	 */
+	if (count >= (1UL << COUNT_COMMIT_ORDER))
+		return;
 	if (chain_len > 100)
 		dbg_printf("WARNING: large chain length: %u.\n",
 			   chain_len);
@@ -1088,3 +1110,32 @@ void cds_lfht_resize_lazy(struct cds_lfht *ht, struct rcu_table *t, int growth)
 		CMM_STORE_SHARED(t->resize_initiated, 1);
 	}
 }
+
+#if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF)
+
+static
+unsigned long resize_target_update_count(struct rcu_table *t,
+				   unsigned long count)
+{
+	return uatomic_set(&t->resize_target, count);
+}
+
+static
+void cds_lfht_resize_lazy_count(struct cds_lfht *ht, struct rcu_table *t,
+				unsigned long count)
+{
+	struct rcu_resize_work *work;
+	unsigned long target_size;
+
+	target_size = resize_target_update_count(t, count);
+	if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
+		uatomic_inc(&ht->in_progress_resize);
+		cmm_smp_mb();	/* increment resize count before calling it */
+		work = malloc(sizeof(*work));
+		work->ht = ht;
+		ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
+		CMM_STORE_SHARED(t->resize_initiated, 1);
+	}
+}
+
+#endif