#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))
#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 {
* 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
}
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;
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));
}
}
}
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));
}
}
}
}
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)
{
}
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);
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_max(&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