From patchwork Sat Jul 18 20:03:44 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Fischofer X-Patchwork-Id: 51261 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-la0-f72.google.com (mail-la0-f72.google.com [209.85.215.72]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 3906E22A28 for ; Sat, 18 Jul 2015 20:18:14 +0000 (UTC) Received: by lagw2 with SMTP id w2sf32962306lag.3 for ; Sat, 18 Jul 2015 13:18:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:delivered-to:from:to:date :message-id:in-reply-to:references:cc:subject:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:list-subscribe :mime-version:content-type:content-transfer-encoding:errors-to :sender:x-original-sender:x-original-authentication-results :mailing-list; bh=QibDzEBHY+yWvg09/7EmlM2MuGxQLCJNM8uxS8BRlbA=; b=jJIQt+EL+0j4iAyaye440NrY3U1RQNmWMOGIizGRYPJBQ2JxF5fPUvdToGVegHVLRY lIzAy+FEWFSrm04SKESqgCDe8Vw2ptz5POQ+prp/Ci6DrAM3SMq6hwsd+UIbH+sNcPAH AixrWYwy2EwOTeFfGYfEYXFtIsAhvlU+rQGwgkKhEZqkqa6MXD+QEzo5MHFgB/JJkwuJ bl+THrkp1Okayaixf77Mm4z1C4Y/ifHRR4OEGd61O5qWdZlonM+CQUSnulOPRCFv/X6O BH2H2HMKgRji+GOWRSSGPk+ozYJN+18sT8u4qA8r6LG0qWPBcPdSSaMbexDijd7NQunv Vnmg== X-Gm-Message-State: ALoCoQml83+++DKatRHohEVLDdQ17WsF4EmsmoMkr2LyijDfQ35mQlIpa+4u0pyYBMSus49KaxW/ X-Received: by 10.112.85.69 with SMTP id f5mr10828004lbz.23.1437250692820; Sat, 18 Jul 2015 13:18:12 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.20.201 with SMTP id p9ls659743lae.42.gmail; Sat, 18 Jul 2015 13:18:12 -0700 (PDT) X-Received: by 10.152.1.66 with SMTP id 2mr20867202lak.56.1437250692653; Sat, 18 Jul 2015 13:18:12 -0700 (PDT) Received: from mail-la0-f46.google.com (mail-la0-f46.google.com. [209.85.215.46]) by mx.google.com with ESMTPS id f10si13442739laf.15.2015.07.18.13.18.12 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 18 Jul 2015 13:18:12 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.46 as permitted sender) client-ip=209.85.215.46; Received: by laem6 with SMTP id m6so77330841lae.0 for ; Sat, 18 Jul 2015 13:18:12 -0700 (PDT) X-Received: by 10.112.209.106 with SMTP id ml10mr20045685lbc.112.1437250691924; Sat, 18 Jul 2015 13:18:11 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.108.230 with SMTP id hn6csp537727lbb; Sat, 18 Jul 2015 13:18:10 -0700 (PDT) X-Received: by 10.140.20.204 with SMTP id 70mr35864083qgj.26.1437250689860; Sat, 18 Jul 2015 13:18:09 -0700 (PDT) Received: from lists.linaro.org (lists.linaro.org. [54.225.227.206]) by mx.google.com with ESMTP id 80si18676627qkv.36.2015.07.18.13.18.09; Sat, 18 Jul 2015 13:18:09 -0700 (PDT) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.225.227.206 as permitted sender) client-ip=54.225.227.206; Received: by lists.linaro.org (Postfix, from userid 109) id 1C65161CAF; Sat, 18 Jul 2015 20:18:09 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, URIBL_BLOCKED autolearn=disabled version=3.4.0 Received: from ip-10-142-244-252.ec2.internal (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id 466C361D21; Sat, 18 Jul 2015 20:06:06 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id DA15A61CA6; Sat, 18 Jul 2015 20:04:44 +0000 (UTC) Received: from mail-oi0-f49.google.com (mail-oi0-f49.google.com [209.85.218.49]) by lists.linaro.org (Postfix) with ESMTPS id 0F10361CBD for ; Sat, 18 Jul 2015 20:04:08 +0000 (UTC) Received: by oihq81 with SMTP id q81so88761777oih.2 for ; Sat, 18 Jul 2015 13:04:07 -0700 (PDT) X-Received: by 10.202.66.6 with SMTP id p6mr11264971oia.49.1437249847616; Sat, 18 Jul 2015 13:04:07 -0700 (PDT) Received: from localhost.localdomain (cpe-24-28-70-239.austin.res.rr.com. [24.28.70.239]) by smtp.gmail.com with ESMTPSA id y5sm8537998oes.15.2015.07.18.13.04.06 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 18 Jul 2015 13:04:07 -0700 (PDT) From: Bill Fischofer To: lng-odp@lists.linaro.org Date: Sat, 18 Jul 2015 15:03:44 -0500 Message-Id: <1437249827-578-10-git-send-email-bill.fischofer@linaro.org> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1437249827-578-1-git-send-email-bill.fischofer@linaro.org> References: <1437249827-578-1-git-send-email-bill.fischofer@linaro.org> X-Topics: timers patch Cc: Barry Spinney Subject: [lng-odp] [RFC API-NEXT PATCH 09/12] linux-generic: tm: add timer_wheel support routines X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: bill.fischofer@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.46 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 Signed-off-by: Barry Spinney Signed-off-by: Mike Holmes Signed-off-by: Bill Fischofer --- platform/linux-generic/Makefile.am | 2 + .../include/odp_timer_wheel_internal.h | 62 ++ platform/linux-generic/odp_timer_wheel.c | 897 +++++++++++++++++++++ 3 files changed, 961 insertions(+) create mode 100644 platform/linux-generic/include/odp_timer_wheel_internal.h create mode 100644 platform/linux-generic/odp_timer_wheel.c diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am index 358a478..393c066 100644 --- a/platform/linux-generic/Makefile.am +++ b/platform/linux-generic/Makefile.am @@ -133,6 +133,7 @@ noinst_HEADERS = \ ${srcdir}/include/odp_name_table_internal.h \ ${srcdir}/include/odp_pkt_queue_internal.h \ ${srcdir}/include/odp_sorted_list_internal.h \ + ${srcdir}/include/odp_timer_wheel_internal.h \ ${srcdir}/Makefile.inc __LIB__libodp_la_SOURCES = \ @@ -147,6 +148,7 @@ __LIB__libodp_la_SOURCES = \ odp_name_table.c \ odp_pkt_queue.c \ odp_sorted_list.c \ + odp_timer_wheel.c \ odp_impl.c \ odp_packet.c \ odp_packet_flags.c \ diff --git a/platform/linux-generic/include/odp_timer_wheel_internal.h b/platform/linux-generic/include/odp_timer_wheel_internal.h new file mode 100644 index 0000000..77744dc --- /dev/null +++ b/platform/linux-generic/include/odp_timer_wheel_internal.h @@ -0,0 +1,62 @@ +/* Copyright 2015 EZchip Semiconductor Ltd. All Rights Reserved. + * + * Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#ifndef ODP_INT_TIMER_WHEEL_H_ +#define ODP_INT_TIMER_WHEEL_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include + +/* Note that ALL times in this API are in units of processor/cpu clock + * cycles! + */ +typedef uint64_t odp_timer_wheel_t; + +#define ODP_INT_TIMER_WHEEL_INVALID 0 + +odp_timer_wheel_t odp_timer_wheel_create(uint32_t max_concurrent_timers, + uint64_t current_time); + +/* odp_int_timer_wheel_curr_time_update should be called before the first + * call to odp_int_timer_wheel_insert, odp_int_timer_wheel_next, etc.. + * It returns > 0 if there are timers expired. + * + */ +uint32_t odp_timer_wheel_curr_time_update(odp_timer_wheel_t timer_wheel, + uint64_t current_time); + +/* Maximum wakeup_time is 100 seconds in the future (though a wakeup time + * greater than a dozen seconds or so is of questionable value), and in + * addition the wakeup_time MUST represent a time in the future. Note that + * the user_ptr cannot be NULL and must be aligned to an 4-byte boundary + * (i.e. the bottom 2 bits of this ptr must be 0). AGAIN THIS MUST BE + * STRESSED - user_ptr is not an arbitrary 64-bit pointer, BUT MUST be + * non-zero and have its bottom two bits being 0! + */ +int odp_timer_wheel_insert(odp_timer_wheel_t timer_wheel, + uint64_t wakeup_time, + void *user_ptr); + +/* Returns the exact same user_ptr value as was passed to + * odp_int_timer_wheel_insert(). + */ +void *odp_timer_wheel_next_expired(odp_timer_wheel_t timer_wheel); + +void odp_timer_wheel_stats_print(odp_timer_wheel_t timer_wheel); + +void odp_timer_wheel_destroy(odp_timer_wheel_t timer_wheel); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/platform/linux-generic/odp_timer_wheel.c b/platform/linux-generic/odp_timer_wheel.c new file mode 100644 index 0000000..fbf3ffc --- /dev/null +++ b/platform/linux-generic/odp_timer_wheel.c @@ -0,0 +1,897 @@ +/* Copyright 2015 EZchip Semiconductor Ltd. All Rights Reserved. + * + * Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#include +#include +#include +#include +#include +#include +#include + +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) + +/* The following constants can be changed either at compile time or run time + * as long as the following constraints are met (by the way REV stands for + * REVOLUTION, i.e. one complete sweep through a specific timer wheel): + */ +#define CYCLES_TO_TICKS_SHIFT 8 +#define CYCLES_PER_TICK (1 << CYCLES_TO_TICKS_SHIFT) +#define CURRENT_TIMER_SLOTS 8192 +#define LEVEL1_TIMER_SLOTS 2048 +#define LEVEL2_TIMER_SLOTS 1024 +#define LEVEL3_TIMER_SLOTS 1024 + +/* The following values are derived and should generally not be changed. The + * basic idea is that the ticks per current timer wheel slot should always be + * 1, since that defines what a tick is - namely the time period of a single + * current timer wheel slot. Then for all levels (including current), the + * ticks per revolution is clearly equal to the ticks per slot times the + * number of slots. Finally the ticks per slot for levels 1 thru 3, must be + * the ticks per revolution of the previous level divided by a small power of + * 2 - e.g. 2, 4, 8, 16 - (but not 1). The idea being that when an upper + * level slot is processed, its entries will be spread across this fraction of + * the lower level wheel and we want to make sure that none of these entries + * is near the lower level's current index. Currently we use 4 for all + * levels. + */ +#define CURRENT_GEAR_RATIO 4 +#define LEVEL1_GEAR_RATIO 4 +#define LEVEL2_GEAR_RATIO 4 +#define TICKS_PER_CURRENT_SLOT 1 +#define TICKS_PER_CURRENT_REV (CURRENT_TIMER_SLOTS * TICKS_PER_CURRENT_SLOT) +#define TICKS_PER_LEVEL1_SLOT (TICKS_PER_CURRENT_REV / CURRENT_GEAR_RATIO) +#define TICKS_PER_LEVEL1_REV (LEVEL1_TIMER_SLOTS * TICKS_PER_LEVEL1_SLOT) +#define TICKS_PER_LEVEL2_SLOT (TICKS_PER_LEVEL1_REV / LEVEL1_GEAR_RATIO) +#define TICKS_PER_LEVEL2_REV (LEVEL2_TIMER_SLOTS * TICKS_PER_LEVEL2_SLOT) +#define TICKS_PER_LEVEL3_SLOT (TICKS_PER_LEVEL2_REV / LEVEL2_GEAR_RATIO) +#define TICKS_PER_LEVEL3_REV (LEVEL3_TIMER_SLOTS * TICKS_PER_LEVEL3_SLOT) + +#define EXPIRED_RING_ENTRIES 64 + +typedef struct timer_blk_s timer_blk_t; + +typedef struct { /* Should be 120 bytes long */ + uint64_t user_data[15]; +} current_blk_t; + +typedef struct { /* Should be 120 bytes long */ + uint64_t user_data[10]; + uint32_t wakeup32[10]; +} general_blk_t; + +/* Must be exactly 128 bytes long AND cacheline aligned! */ +struct timer_blk_s { + timer_blk_t *next_timer_blk; + union { + current_blk_t current_blk; + general_blk_t general_blk; + }; +}; + +/* Each current_timer_slot is 8 bytes long. */ +typedef union { + /* The selection of which union element to use is based on the LSB + * bit, under the required assumption that both of these pointers are + * at least 8-byte aligned. If the entire 8 bytes is zero, then this + * entry is empty, otherwise a LSB bit of 0 indicates a timer_blk_list + * and a LSB bit of 1 indicates a single entry with a 64-bit user_data + * word. + */ + uint64_t user_data; + timer_blk_t *timer_blk_list; +} current_timer_slot_t; + +typedef struct { + current_timer_slot_t slots[0]; +} current_wheel_t; + +typedef struct { + uint32_t count; + uint32_t peak_count; + uint32_t expired_ring_full_cnt; + uint32_t head_idx; + uint32_t tail_idx; + uint32_t max_idx; + current_timer_slot_t entries[0]; +} expired_ring_t; + +typedef struct { + uint32_t kind; /* 1 for single_entry_t */ + uint32_t wakeup32; + uint64_t user_data; +} single_entry_t; + +typedef struct { + uint32_t kind; /* 2 for list_entry_t */ + uint32_t num_blks; + timer_blk_t *timer_blk_list; +} list_entry_t; + +typedef union { /* Each general_timer_slot is 16 bytes long. */ + /* The selection of which union element to use is based on the first 4 + * byte field which is always the "kind". If kind is 0, then this + * slot is empty, else if the kind is 1 then it is a single_entry and + * if the kind is 2 then it is a list_entry. + */ + single_entry_t single_entry; + list_entry_t list_entry; +} general_timer_slot_t; + +typedef struct { + general_timer_slot_t slots[0]; +} general_wheel_t; + +typedef struct { + /* Note that rev stands for revolution - one complete sweep through + * this timer wheel. + */ + uint16_t num_slots; /* Must be a power of 2. */ + uint16_t slot_idx; + uint16_t gear_mask; /* = (num_slots / gear_ratio) - 1 */ + uint16_t gear_ratio; /* num of next level wheel updates per this + * rev + */ + uint32_t ticks_shift; + uint32_t ticks_per_slot; /* Must be a power of 2. */ + uint64_t ticks_per_rev; /* = num_slots * ticks_per_slot */ + uint64_t max_ticks; /* = current_ticks + ticks_per_rev */ +} wheel_desc_t; + +typedef struct { + uint32_t last_slot_served; + uint32_t free_list_size; + uint32_t min_free_list_size; + uint32_t peak_free_list_size; + timer_blk_t *free_list_head; + uint64_t total_timer_inserts; + uint64_t insert_fail_cnt; + uint64_t total_timer_removes; + uint64_t total_promote_cnt; + uint64_t promote_fail_cnt; + uint64_t current_ticks; + wheel_desc_t wheel_descs[4]; + current_wheel_t *current_wheel; + general_wheel_t *general_wheels[3]; + expired_ring_t *expired_timers_ring; +} timer_wheels_t; + +static uint32_t odp_internal_ilog2(uint64_t value) +{ + uint64_t pwr_of_2; + uint32_t bit_shift; + + for (bit_shift = 0; bit_shift < 64; bit_shift++) { + pwr_of_2 = 1 << bit_shift; + if (value == pwr_of_2) + return bit_shift; + else if (value < pwr_of_2) + return bit_shift - 1; + } + + return 64; +} + +static inline uint32_t timer_wheel_slot_idx_inc(uint32_t slot_idx, + uint32_t num_slots) +{ + slot_idx++; + if (slot_idx < num_slots) + return slot_idx; + else + return 0; +} + +static current_wheel_t *current_wheel_alloc(timer_wheels_t *timer_wheels, + uint32_t desc_idx) +{ + current_wheel_t *current_wheel; + wheel_desc_t *wheel_desc; + uint64_t ticks_per_slot, current_ticks, adjusted_ticks; + uint64_t ticks_per_rev; + uint32_t num_slots, malloc_len; + + wheel_desc = &timer_wheels->wheel_descs[desc_idx]; + num_slots = wheel_desc->num_slots; + ticks_per_slot = 1; + malloc_len = num_slots * sizeof(current_timer_slot_t); + current_wheel = malloc(malloc_len); + memset(current_wheel, 0, malloc_len); + + current_ticks = timer_wheels->current_ticks; + adjusted_ticks = current_ticks & (ticks_per_slot - 1); + ticks_per_rev = num_slots; + + wheel_desc->ticks_per_rev = ticks_per_rev; + wheel_desc->ticks_shift = 0; + wheel_desc->max_ticks = adjusted_ticks + ticks_per_rev; + wheel_desc->gear_mask = (num_slots / wheel_desc->gear_ratio) - 1; + return current_wheel; +} + +static general_wheel_t *general_wheel_alloc(timer_wheels_t *timer_wheels, + uint32_t desc_idx) +{ + general_wheel_t *general_wheel; + wheel_desc_t *wheel_desc; + uint64_t ticks_per_slot, current_ticks, adjusted_ticks; + uint64_t ticks_per_rev; + uint32_t num_slots, malloc_len; + + wheel_desc = &timer_wheels->wheel_descs[desc_idx]; + num_slots = wheel_desc->num_slots; + ticks_per_slot = (uint64_t)wheel_desc->ticks_per_slot; + malloc_len = num_slots * sizeof(general_timer_slot_t); + general_wheel = malloc(malloc_len); + memset(general_wheel, 0, malloc_len); + + current_ticks = timer_wheels->current_ticks; + adjusted_ticks = current_ticks & (ticks_per_slot - 1); + ticks_per_rev = num_slots * ticks_per_slot; + + wheel_desc->ticks_per_rev = ticks_per_rev; + wheel_desc->ticks_shift = odp_internal_ilog2(ticks_per_slot); + wheel_desc->max_ticks = adjusted_ticks + ticks_per_rev; + wheel_desc->gear_mask = (num_slots / wheel_desc->gear_ratio) - 1; + return general_wheel; +} + +static int expired_ring_create(timer_wheels_t *timer_wheels, + uint32_t num_entries) +{ + expired_ring_t *expired_ring; + uint32_t malloc_len; + + malloc_len = sizeof(expired_ring_t) + + (sizeof(current_timer_slot_t) * num_entries); + expired_ring = malloc(malloc_len); + memset(expired_ring, 0, malloc_len); + expired_ring->max_idx = num_entries - 1; + + timer_wheels->expired_timers_ring = expired_ring; + return 0; +} + +static int free_list_add(timer_wheels_t *timer_wheels, + uint32_t num_timer_blks) +{ + timer_blk_t *block_of_timer_blks, *timer_blk, *next_timer_blk; + uint32_t malloc_len, idx; + + malloc_len = num_timer_blks * sizeof(timer_blk_t); + /* Should be cacheline aligned! */ + block_of_timer_blks = malloc(malloc_len); + if (!block_of_timer_blks) + return -1; + + memset(block_of_timer_blks, 0, malloc_len); + + /* Link these timer_blks together. */ + timer_blk = block_of_timer_blks; + next_timer_blk = timer_blk + 1; + for (idx = 0; idx < num_timer_blks; idx++) { + timer_blk->next_timer_blk = next_timer_blk; + timer_blk = next_timer_blk; + next_timer_blk++; + } + + timer_blk->next_timer_blk = timer_wheels->free_list_head; + timer_wheels->free_list_size += num_timer_blks; + timer_wheels->free_list_head = block_of_timer_blks; + if (timer_wheels->peak_free_list_size < timer_wheels->free_list_size) + timer_wheels->peak_free_list_size = + timer_wheels->free_list_size; + return 0; +} + +static timer_blk_t *timer_blk_alloc(timer_wheels_t *timer_wheels) +{ + timer_blk_t *head_timer_blk; + int rc; + + if (timer_wheels->free_list_size <= 1) { + /* Replenish the timer_blk_t free list. */ + timer_wheels->min_free_list_size = timer_wheels->free_list_size; + rc = free_list_add(timer_wheels, 1024); + if (rc < 0) + return NULL; + } + + head_timer_blk = timer_wheels->free_list_head; + timer_wheels->free_list_size--; + timer_wheels->free_list_head = head_timer_blk->next_timer_blk; + if (timer_wheels->free_list_size < timer_wheels->min_free_list_size) + timer_wheels->min_free_list_size = timer_wheels->free_list_size; + + memset(head_timer_blk, 0, sizeof(timer_blk_t)); + return head_timer_blk; +} + +static void timer_blk_free(timer_wheels_t *timer_wheels, + timer_blk_t *timer_blk) +{ + timer_blk->next_timer_blk = timer_wheels->free_list_head; + timer_wheels->free_list_head = timer_blk; + timer_wheels->free_list_size++; + if (timer_wheels->peak_free_list_size < timer_wheels->free_list_size) + timer_wheels->peak_free_list_size = + timer_wheels->free_list_size; +} + +static int current_wheel_insert(timer_wheels_t *timer_wheels, + uint32_t wakeup_ticks, + uint64_t user_data) +{ + current_timer_slot_t *timer_slot; + current_wheel_t *current_wheel; + wheel_desc_t *wheel_desc; + timer_blk_t *new_timer_blk, *timer_blk; + uint64_t num_slots; + uint32_t wheel_idx, idx; + + /* To reach here it must be the case that (wakeup_ticks - + * current_ticks) is < current_wheel->num_slots. + */ + wheel_desc = &timer_wheels->wheel_descs[0]; + current_wheel = timer_wheels->current_wheel; + num_slots = (uint64_t)wheel_desc->num_slots; + wheel_idx = (uint32_t)(wakeup_ticks & (num_slots - 1)); + timer_slot = ¤t_wheel->slots[wheel_idx]; + + /* Three cases: (a) the timer_slot is currently empty, (b) the + * timer_slot contains a single user_data word directly inside it or + * (c) the timer_slot contains a pointer to a linked list of + * timer_blk's. + */ + if (timer_slot->user_data == 0) { /* case (a) */ + timer_slot->user_data = user_data | 0x01; + } else if ((timer_slot->user_data & 0x3) == 0x01) { /* case (b) */ + /* Need to promote this pre-existing single user_data plus the + * new user_data into a timer_blk with two entries. + */ + new_timer_blk = timer_blk_alloc(timer_wheels); + if (!new_timer_blk) + return -1; + + new_timer_blk->next_timer_blk = NULL; + new_timer_blk->current_blk.user_data[0] = timer_slot->user_data; + new_timer_blk->current_blk.user_data[1] = user_data; + timer_slot->timer_blk_list = new_timer_blk; + } else { /* case (c) */ + /* First try to find an empty slot in the current timer_blk. */ + timer_blk = timer_slot->timer_blk_list; + for (idx = 0; idx < 15; idx++) { + if (timer_blk->current_blk.user_data[idx] == 0) { + timer_blk->current_blk.user_data[idx] = + user_data; + return 0; + } + } + + /* current timer_blk is full, so we need to allocate a new one + * and link it in. + */ + new_timer_blk = timer_blk_alloc(timer_wheels); + if (!new_timer_blk) + return -1; + + new_timer_blk->next_timer_blk = timer_blk; + new_timer_blk->current_blk.user_data[0] = user_data; + timer_slot->timer_blk_list = new_timer_blk; + } + + return 0; +} + +static int general_wheel_insert(timer_wheels_t *timer_wheels, + uint32_t desc_idx, + uint32_t wakeup_ticks, + uint64_t user_data) +{ + general_timer_slot_t *timer_slot; + general_wheel_t *general_wheel; + wheel_desc_t *wheel_desc; + timer_blk_t *new_timer_blk, *timer_blk; + uint64_t num_slots, old_user_data; + uint32_t wheel_idx, wakeup32, kind, old_wakeup32, idx; + + wheel_desc = &timer_wheels->wheel_descs[desc_idx]; + general_wheel = timer_wheels->general_wheels[desc_idx - 1]; + num_slots = (uint64_t)wheel_desc->num_slots; + wakeup32 = (uint32_t)(wakeup_ticks & 0xFFFFFFFF); + wakeup_ticks = wakeup_ticks >> wheel_desc->ticks_shift; + wheel_idx = (uint32_t)(wakeup_ticks & (num_slots - 1)); + timer_slot = &general_wheel->slots[wheel_idx]; + kind = timer_slot->single_entry.kind; + + /* Three cases: (a) the timer_slot is currently empty, (b) the + * timer_slot contains a single user_data word directly inside it or + * (c) the timer_slot contains a pointer to a linked list of + * timer_blk's. + */ + if (kind == 0) { /* case (a) */ + timer_slot->single_entry.kind = 1; + timer_slot->single_entry.wakeup32 = wakeup32; + timer_slot->single_entry.user_data = user_data; + } else if (kind == 1) { /* case (b) */ + /* Need to promote this single entry plus the new user_data + * into a timer_blk with two entries. + */ + new_timer_blk = timer_blk_alloc(timer_wheels); + if (!new_timer_blk) + return -1; + + old_user_data = timer_slot->single_entry.user_data; + old_wakeup32 = timer_slot->single_entry.wakeup32; + + new_timer_blk->next_timer_blk = NULL; + new_timer_blk->general_blk.user_data[0] = old_user_data; + new_timer_blk->general_blk.wakeup32[0] = old_wakeup32; + new_timer_blk->general_blk.user_data[1] = user_data; + new_timer_blk->general_blk.wakeup32[1] = wakeup32; + timer_slot->list_entry.kind = 2; + timer_slot->list_entry.num_blks = 1; + timer_slot->list_entry.timer_blk_list = new_timer_blk; + } else { /* case (c) */ + /* First try to find an empty slot in the first timer_blk. */ + timer_blk = timer_slot->list_entry.timer_blk_list; + for (idx = 0; idx < 10; idx++) { + if (timer_blk->general_blk.user_data[idx] == 0) { + timer_blk->general_blk.user_data[idx] = + user_data; + timer_blk->general_blk.wakeup32[idx] = + wakeup32; + return 0; + } + } + + /* The first timer_blk is full, so we need to allocate a new + * one and link it in. + */ + new_timer_blk = timer_blk_alloc(timer_wheels); + if (!new_timer_blk) + return -1; + + new_timer_blk->next_timer_blk = timer_blk; + new_timer_blk->general_blk.user_data[0] = user_data; + new_timer_blk->general_blk.wakeup32[0] = wakeup32; + timer_slot->list_entry.kind = 2; + timer_slot->list_entry.num_blks++; + timer_slot->list_entry.timer_blk_list = new_timer_blk; + } + + return 0; +} + +static int expired_timers_append(timer_wheels_t *timer_wheels, + current_timer_slot_t *timer_slot) +{ + expired_ring_t *expired_ring; + uint32_t tail_idx; + + /* Append either this single entry or the entire timer_blk_list to the + * ring of expired_timers. + */ + expired_ring = timer_wheels->expired_timers_ring; + if (expired_ring->max_idx <= expired_ring->count) + return -1; + + tail_idx = expired_ring->tail_idx; + expired_ring->entries[tail_idx] = *timer_slot; + tail_idx++; + if (expired_ring->max_idx < tail_idx) + tail_idx = 0; + + expired_ring->tail_idx = tail_idx; + expired_ring->count++; + if (expired_ring->peak_count < expired_ring->count) + expired_ring->peak_count = expired_ring->count; + return 0; +} + +static int timer_blk_list_search(timer_wheels_t *timer_wheels, + current_timer_slot_t *head_entry, + uint64_t *user_data_ptr) +{ + timer_blk_t *timer_blk, *next_timer_blk; + uint64_t user_data; + uint32_t idx; + + timer_blk = head_entry->timer_blk_list; + while (timer_blk) { + for (idx = 0; idx < 15; idx++) { + user_data = timer_blk->current_blk.user_data[idx]; + if (user_data != 0) { + *user_data_ptr = + timer_blk->current_blk.user_data[idx]; + timer_blk->current_blk.user_data[idx] = 0; + return 1; + } + } + + next_timer_blk = timer_blk->next_timer_blk; + timer_blk_free(timer_wheels, timer_blk); + timer_blk = next_timer_blk; + } + + return 0; +} + +static int expired_timers_remove(timer_wheels_t *timer_wheels, + uint64_t *user_data_ptr) +{ + current_timer_slot_t *head_entry; + expired_ring_t *expired_ring; + uint32_t head_idx; + int rc; + + expired_ring = timer_wheels->expired_timers_ring; + if (expired_ring->count == 0) + return 0; + + head_idx = expired_ring->head_idx; + head_entry = &expired_ring->entries[head_idx]; + if ((head_entry->user_data & 0x3) == 1) { + *user_data_ptr = head_entry->user_data; + expired_ring->entries[head_idx].user_data = 0; + head_idx++; + if (expired_ring->max_idx < head_idx) + head_idx = 0; + + expired_ring->head_idx = head_idx; + expired_ring->count--; + return 1; + } + + /* Search timer_blk_list for non-empty user_data values. */ + rc = timer_blk_list_search(timer_wheels, head_entry, user_data_ptr); + if (0 < rc) + return rc; + + /* Advance to use the next ring entry. */ + expired_ring->entries[head_idx].user_data = 0; + head_idx++; + if (expired_ring->max_idx < head_idx) + head_idx = 0; + + expired_ring->head_idx = head_idx; + expired_ring->count--; + + head_entry = &expired_ring->entries[head_idx]; + return timer_blk_list_search(timer_wheels, head_entry, user_data_ptr); +} + +static int timer_current_wheel_update(timer_wheels_t *timer_wheels, + uint32_t elapsed_ticks) +{ + current_timer_slot_t *timer_slot; + current_wheel_t *current_wheel; + wheel_desc_t *wheel_desc; + uint64_t max_ticks; + uint32_t num_slots, slot_idx, max_cnt, cnt; + int ret_code, rc; + + /* Advance current wheel for each elapsed tick, up to a maximum. */ + wheel_desc = &timer_wheels->wheel_descs[0]; + slot_idx = wheel_desc->slot_idx; + num_slots = wheel_desc->num_slots; + max_ticks = wheel_desc->max_ticks; + max_cnt = (uint32_t)MIN(elapsed_ticks, 15); + current_wheel = timer_wheels->current_wheel; + ret_code = 0; + + for (cnt = 1; cnt <= max_cnt; cnt++) { + ret_code |= (slot_idx & wheel_desc->gear_mask) == 0; + timer_slot = ¤t_wheel->slots[slot_idx]; + if (timer_slot->user_data != 0) { + rc = expired_timers_append(timer_wheels, timer_slot); + if (rc < 0) + timer_wheels-> + expired_timers_ring-> + expired_ring_full_cnt++; + + timer_slot->user_data = 0; + } + + timer_wheels->current_ticks++; + max_ticks++; + slot_idx = timer_wheel_slot_idx_inc(slot_idx, num_slots); + } + + wheel_desc->slot_idx = slot_idx; + wheel_desc->max_ticks = max_ticks; + return ret_code; +} + +static int odp_int_timer_wheel_promote(timer_wheels_t *timer_wheels, + uint32_t desc_idx, + uint64_t wakeup_ticks, + uint64_t user_data) +{ + if (desc_idx == 0) + return current_wheel_insert(timer_wheels, + wakeup_ticks, user_data); + else + return general_wheel_insert(timer_wheels, + desc_idx, wakeup_ticks, + user_data); +} + +static void timer_wheel_slot_promote(timer_wheels_t *timer_wheels, + uint32_t desc_idx, + general_timer_slot_t *timer_slot) +{ + general_blk_t *general_blk; + timer_blk_t *timer_blk, *next_timer_blk; + uint64_t user_data, current_ticks, + current_ticks_msb, wakeup_ticks; + uint32_t idx, wakeup32; + int rc; + + current_ticks = timer_wheels->current_ticks; + current_ticks_msb = (current_ticks >> 32) << 32; + if (timer_slot->single_entry.kind == 1) { + user_data = timer_slot->single_entry.user_data; + wakeup32 = timer_slot->single_entry.wakeup32; + wakeup_ticks = current_ticks_msb | (uint64_t)wakeup32; + if (wakeup_ticks < current_ticks) + wakeup_ticks += 1ULL << 32; + + rc = odp_int_timer_wheel_promote(timer_wheels, desc_idx, + wakeup_ticks, user_data); + if (rc < 0) + timer_wheels->promote_fail_cnt++; + else + timer_wheels->total_promote_cnt++; + return; + } + + timer_blk = timer_slot->list_entry.timer_blk_list; + while (timer_blk) { + general_blk = &timer_blk->general_blk; + for (idx = 0; idx < 10; idx++) { + user_data = general_blk->user_data[idx]; + if (user_data == 0) + break; + + wakeup32 = general_blk->wakeup32[idx]; + wakeup_ticks = current_ticks_msb | (uint64_t)wakeup32; + if (wakeup_ticks < current_ticks) + wakeup_ticks += 1ULL << 32; + + rc = odp_int_timer_wheel_promote(timer_wheels, + desc_idx, + wakeup_ticks, + user_data); + if (rc < 0) + timer_wheels->promote_fail_cnt++; + else + timer_wheels->total_promote_cnt++; + } + + next_timer_blk = timer_blk->next_timer_blk; + timer_blk_free(timer_wheels, timer_blk); + timer_blk = next_timer_blk; + } +} + +static int timer_general_wheel_update(timer_wheels_t *timer_wheels, + uint32_t desc_idx) +{ + general_timer_slot_t *timer_slot; + general_wheel_t *general_wheel; + wheel_desc_t *wheel_desc; + uint32_t num_slots, slot_idx; + int ret_code; + + wheel_desc = &timer_wheels->wheel_descs[desc_idx]; + slot_idx = wheel_desc->slot_idx; + num_slots = wheel_desc->num_slots; + general_wheel = timer_wheels->general_wheels[desc_idx - 1]; + timer_slot = &general_wheel->slots[slot_idx]; + ret_code = (slot_idx & wheel_desc->gear_mask) == 0; + + if (timer_slot->single_entry.kind != 0) { + timer_wheel_slot_promote(timer_wheels, + desc_idx - 1, timer_slot); + timer_slot->single_entry.kind = 0; + } + + wheel_desc->max_ticks++; + wheel_desc->slot_idx = timer_wheel_slot_idx_inc(slot_idx, num_slots); + return ret_code; +} + +odp_timer_wheel_t odp_timer_wheel_create(uint32_t max_concurrent_timers, + uint64_t current_time) +{ + timer_wheels_t *timer_wheels; + uint64_t current_ticks; + int rc; + + timer_wheels = malloc(sizeof(timer_wheels_t)); + current_ticks = current_time >> CYCLES_TO_TICKS_SHIFT; + timer_wheels->current_ticks = current_ticks; + + timer_wheels->wheel_descs[0].num_slots = CURRENT_TIMER_SLOTS; + timer_wheels->wheel_descs[1].num_slots = LEVEL1_TIMER_SLOTS; + timer_wheels->wheel_descs[2].num_slots = LEVEL2_TIMER_SLOTS; + timer_wheels->wheel_descs[3].num_slots = LEVEL3_TIMER_SLOTS; + + timer_wheels->wheel_descs[0].gear_ratio = CURRENT_GEAR_RATIO; + timer_wheels->wheel_descs[1].gear_ratio = LEVEL1_GEAR_RATIO; + timer_wheels->wheel_descs[2].gear_ratio = LEVEL2_GEAR_RATIO; + timer_wheels->wheel_descs[3].gear_ratio = 1; + + timer_wheels->wheel_descs[0].ticks_per_slot = TICKS_PER_CURRENT_SLOT; + timer_wheels->wheel_descs[1].ticks_per_slot = TICKS_PER_LEVEL1_SLOT; + timer_wheels->wheel_descs[2].ticks_per_slot = TICKS_PER_LEVEL2_SLOT; + timer_wheels->wheel_descs[3].ticks_per_slot = TICKS_PER_LEVEL3_SLOT; + + timer_wheels->current_wheel = current_wheel_alloc(timer_wheels, 0); + timer_wheels->general_wheels[0] = general_wheel_alloc(timer_wheels, 1); + timer_wheels->general_wheels[1] = general_wheel_alloc(timer_wheels, 2); + timer_wheels->general_wheels[2] = general_wheel_alloc(timer_wheels, 3); + + rc = expired_ring_create(timer_wheels, EXPIRED_RING_ENTRIES); + if (rc < 0) + return ODP_INT_TIMER_WHEEL_INVALID; + + free_list_add(timer_wheels, max_concurrent_timers / 4); + timer_wheels->min_free_list_size = timer_wheels->free_list_size; + timer_wheels->peak_free_list_size = timer_wheels->free_list_size; + return (odp_timer_wheel_t)timer_wheels; +} + +uint32_t odp_timer_wheel_curr_time_update(odp_timer_wheel_t timer_wheel, + uint64_t current_time) +{ + timer_wheels_t *timer_wheels; + uint64_t new_current_ticks, elapsed_ticks; + uint32_t desc_idx; + int rc; + + timer_wheels = (timer_wheels_t *)timer_wheel; + new_current_ticks = current_time >> CYCLES_TO_TICKS_SHIFT; + elapsed_ticks = new_current_ticks - timer_wheels->current_ticks; + if (elapsed_ticks == 0) + return 0; + + /* Advance current wheel for each elapsed tick, up to a maximum. This + * function returns a value > 0, then the next level's timer wheel + * needs to be updated. + */ + rc = timer_current_wheel_update(timer_wheels, (uint32_t)elapsed_ticks); + + /* See if we need to do any higher wheel advancing or processing.*/ + desc_idx = 1; + while ((0 < rc) && (desc_idx <= 3)) + rc = timer_general_wheel_update(timer_wheels, desc_idx++); + + return timer_wheels->expired_timers_ring->count; +} + +int odp_timer_wheel_insert(odp_timer_wheel_t timer_wheel, + uint64_t wakeup_time, + void *user_ptr) +{ + timer_wheels_t *timer_wheels; + uint64_t user_data, wakeup_ticks; + int rc; + + user_data = (uint64_t)user_ptr; + if (user_data == 0) + return -4; /* user_data cannot be 0! */ + else if ((user_data & 0x3) != 0) + return -5; /* user_data ptr must be at least 4-byte aligned. */ + + timer_wheels = (timer_wheels_t *)timer_wheel; + wakeup_ticks = (wakeup_time >> CYCLES_TO_TICKS_SHIFT) + 1; + if (wakeup_time <= timer_wheels->current_ticks) + return -6; + + if (wakeup_ticks < timer_wheels->wheel_descs[0].max_ticks) + rc = current_wheel_insert(timer_wheels, + wakeup_ticks, user_data); + else if (wakeup_ticks < timer_wheels->wheel_descs[1].max_ticks) + rc = general_wheel_insert(timer_wheels, 1, + wakeup_ticks, user_data); + else if (wakeup_ticks < timer_wheels->wheel_descs[2].max_ticks) + rc = general_wheel_insert(timer_wheels, 2, wakeup_ticks, + user_data); + else if (wakeup_ticks < timer_wheels->wheel_descs[3].max_ticks) + rc = general_wheel_insert(timer_wheels, 3, + wakeup_ticks, user_data); + else + return -1; + + if (rc < 0) + timer_wheels->insert_fail_cnt++; + else + timer_wheels->total_timer_inserts++; + + return rc; +} + +void *odp_timer_wheel_next_expired(odp_timer_wheel_t timer_wheel) + +{ + timer_wheels_t *timer_wheels; + uint64_t user_data; + int rc; + + /* Remove the head of the timer wheel. */ + timer_wheels = (timer_wheels_t *)timer_wheel; + rc = expired_timers_remove(timer_wheels, &user_data); + if (rc <= 0) + return NULL; + + user_data &= ~0x3; + timer_wheels->total_timer_removes++; + return (void *)user_data; +} + +static void odp_int_timer_wheel_desc_print(wheel_desc_t *wheel_desc, + uint32_t wheel_idx) +{ + ODP_DBG(" wheel=%u num_slots=%u ticks_shift=%u ticks_per_slot=%u" + " ticks_per_rev=%lu\n", + wheel_idx, wheel_desc->num_slots, wheel_desc->ticks_shift, + wheel_desc->ticks_per_slot, wheel_desc->ticks_per_rev); +} + +void odp_timer_wheel_stats_print(odp_timer_wheel_t timer_wheel) +{ + timer_wheels_t *timer_wheels; + expired_ring_t *expired_ring; + uint32_t wheel_idx; + + timer_wheels = (timer_wheels_t *)timer_wheel; + expired_ring = timer_wheels->expired_timers_ring; + + ODP_DBG("odp_int_timer_wheel_stats current_ticks=%lu\n", + timer_wheels->current_ticks); + for (wheel_idx = 0; wheel_idx < 4; wheel_idx++) + odp_int_timer_wheel_desc_print( + &timer_wheels->wheel_descs[wheel_idx], + wheel_idx); + + ODP_DBG(" total timer_inserts=%lu timer_removes=%lu " + "insert_fails=%lu\n", + timer_wheels->total_timer_inserts, + timer_wheels->total_timer_removes, + timer_wheels->insert_fail_cnt); + ODP_DBG(" total_promote_cnt=%lu promote_fail_cnt=%lu\n", + timer_wheels->total_promote_cnt, + timer_wheels->promote_fail_cnt); + ODP_DBG(" free_list_size=%u min_size=%u peak_size=%u\n", + timer_wheels->free_list_size, timer_wheels->min_free_list_size, + timer_wheels->peak_free_list_size); + ODP_DBG(" expired_timers_ring size=%u count=%u " + "peak_count=%u full_cnt=%u\n", + expired_ring->max_idx + 1, expired_ring->count, + expired_ring->peak_count, expired_ring->expired_ring_full_cnt); +} + +void odp_timer_wheel_destroy(odp_timer_wheel_t timer_wheel) +{ + timer_wheels_t *timer_wheels; + expired_ring_t *expired_ring; + + timer_wheels = (timer_wheels_t *)timer_wheel; + expired_ring = timer_wheels->expired_timers_ring; + + /* First free all of the block_of_timer_blks @TODO */ + free(timer_wheels->current_wheel); + free(timer_wheels->general_wheels[0]); + free(timer_wheels->general_wheels[1]); + free(timer_wheels->general_wheels[2]); + free(expired_ring); + free(timer_wheels); +}