/* * Copyright (c) 2015 Cisco and/or its affiliates. * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at: * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include #include #include #include void timing_wheel_init (timing_wheel_t * w, u64 current_cpu_time, f64 cpu_clocks_per_second) { if (w->max_sched_time <= w->min_sched_time) { w->min_sched_time = 1e-6; w->max_sched_time = 1e-3; } w->cpu_clocks_per_second = cpu_clocks_per_second; w->log2_clocks_per_bin = max_log2 (w->cpu_clocks_per_second * w->min_sched_time); w->log2_bins_per_wheel = max_log2 (w->cpu_clocks_per_second * w->max_sched_time); w->log2_bins_per_wheel -= w->log2_clocks_per_bin; w->log2_clocks_per_wheel = w->log2_bins_per_wheel + w->log2_clocks_per_bin; w->bins_per_wheel = 1 << w->log2_bins_per_wheel; w->bins_per_wheel_mask = w->bins_per_wheel - 1; w->current_time_index = current_cpu_time >> w->log2_clocks_per_bin; if (w->n_wheel_elt_time_bits <= 0 || w->n_wheel_elt_time_bits >= STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base)) w->n_wheel_elt_time_bits = STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base) - 1; w->cpu_time_base = current_cpu_time; w->time_index_next_cpu_time_base_update = w->current_time_index + ((u64) 1 << (w->n_wheel_elt_time_bits - w->log2_clocks_per_bin)); } always_inline uword get_level_and_relative_time (timing_wheel_t * w, u64 cpu_time, uword * rtime_result) { u64 dt, rtime; uword level_index; dt = (cpu_time >> w->log2_clocks_per_bin); /* Time should always move forward. */ ASSERT (dt >= w->current_time_index); dt -= w->current_time_index; /* Find level and offset within level. Level i has bins of size 2^((i+1)*M) */ rtime = dt; for (level_index = 0; (rtime >> w->log2_bins_per_wheel) != 0; level_index++) rtime = (rtime >> w->log2_bins_per_wheel) - 1; /* Return offset within level and level index. */ ASSERT (rtime < w->bins_per_wheel); *rtime_result = rtime; return level_index; } always_inline uword time_index_to_wheel_index (timing_wheel_t * w, uword level_index, u64 ti) { return (ti >> (level_index * w->log2_bins_per_wheel)) & w->bins_per_wheel_mask; } /* Find current time on this level. */ always_inline uword current_time_wheel_index (timing_wheel_t * w, uword level_index) { return time_index_to_wheel_index (w, level_index, w->current_time_index); } /* Circular wheel indexing. */ always_inline uword wheel_add (timing_wheel_t * w, word x) { return x & w->bins_per_wheel_mask; } always_inline uword rtime_to_wheel_index (timing_wheel_t * w, uword level_index, uword rtime) { uword t = current_time_wheel_index (w, level_index); return wheel_add (w, t + rtime); } static clib_error_t * validate_level (timing_wheel_t * w, uword level_index, uword * n_elts) { timing_wheel_level_t *level; timing_wheel_elt_t *e; uword wi; clib_error_t *error = 0; #define _(x) \ do { \ error = CLIB_ERROR_ASSERT (x); \ ASSERT (! error); \ if (error) return error; \ } while (0) level = vec_elt_at_index (w->levels, level_index); for (wi = 0; wi < vec_len (level->elts); wi++) { /* Validate occupancy bitmap. */ _(clib_bitmap_get_no_check (level->occupancy_bitmap, wi) == (vec_len (level->elts[wi]) > 0)); *n_elts += vec_len (level->elts[wi]); vec_foreach (e, level->elts[wi]) { /* Validate time bin and level. */ u64 e_time; uword e_ti, e_li, e_wi; e_time = e->cpu_time_relative_to_base + w->cpu_time_base; e_li = get_level_and_relative_time (w, e_time, &e_ti); e_wi = rtime_to_wheel_index (w, level_index, e_ti); if (e_li == level_index - 1) /* If this element was scheduled on the previous level it must be wrapped. */ _(e_ti + current_time_wheel_index (w, level_index - 1) >= w->bins_per_wheel); else { _(e_li == level_index); if (e_li == 0) _(e_wi == wi); else _(e_wi == wi || e_wi + 1 == wi || e_wi - 1 == wi); } } } #undef _ return error; } void timing_wheel_validate (timing_wheel_t * w) { uword l; clib_error_t *error = 0; uword n_elts; if (!w->validate) return; n_elts = pool_elts (w->overflow_pool); for (l = 0; l < vec_len (w->levels); l++) { error = validate_level (w, l, &n_elts); if (error) clib_error_report (error); } } always_inline void free_elt_vector (timing_wheel_t * w, timing_wheel_elt_t * ev) { /* Poison free elements so we never use them by mistake. */ if (CLIB_DEBUG > 0) memset (ev, ~0, vec_len (ev) * sizeof (ev[0])); _vec_len (ev) = 0; vec_add1 (w->free_elt_vectors, ev); } static timing_wheel_elt_t * insert_helper (timing_wheel_t * w, uword level_index, uword rtime) { timing_wheel_level_t *level; timing_wheel_elt_t *e; uword wheel_index; /* Circular buffer. */ vec_validate (w->levels, level_index); level = vec_elt_at_index (w->levels, level_index); if (PREDICT_FALSE (!level->elts)) { uword max = w->bins_per_wheel - 1; clib_bitmap_validate (level->occupancy_bitmap, max); vec_validate (level->elts, max); } wheel_index = rtime_to_wheel_index (w, level_index, rtime); level->occupancy_bitmap = clib_bitmap_ori (level->occupancy_bitmap, wheel_index); /* Allocate an elt vector from free list if there is one. */ if (!level->elts[wheel_index] && vec_len (w->free_elt_vectors)) level->elts[wheel_index] = vec_pop (w->free_elt_vectors); /* Add element to vector for this time bin. */ vec_add2 (level->elts[wheel_index], e, 1); return e; } /* Insert user data on wheel at given CPU time stamp. */ static void timing_wheel_insert_helper (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data) { timing_wheel_elt_t *e; u64 dt; uword rtime, level_index; level_index = get_level_and_relative_time (w, insert_cpu_time, &rtime); dt = insert_cpu_time - w->cpu_time_base; if (PREDICT_TRUE (0 == (dt >> BITS (e->cpu_time_relative_to_base)))) { e = insert_helper (w, level_index, rtime); e->user_data = user_data; e->cpu_time_relative_to_base = dt; if (insert_cpu_time < w->cached_min_cpu_time_on_wheel) w->cached_min_cpu_time_on_wheel = insert_cpu_time; } else { /* Time too far in the future: add to overflow vector. */ timing_wheel_overflow_elt_t *oe; pool_get (w->overflow_pool, oe); oe->user_data = user_data; oe->cpu_time = insert_cpu_time; } } always_inline uword elt_is_deleted (timing_wheel_t * w, u32 user_data) { return (hash_elts (w->deleted_user_data_hash) > 0 && hash_get (w->deleted_user_data_hash, user_data)); } static timing_wheel_elt_t * delete_user_data (timing_wheel_elt_t * elts, u32 user_data) { uword found_match; timing_wheel_elt_t *e, *new_elts; /* Quickly scan to see if there are any elements to delete in this bucket. */ found_match = 0; vec_foreach (e, elts) { found_match = e->user_data == user_data; if (found_match) break; } if (!found_match) return elts; /* Re-scan to build vector of new elts with matching user_data deleted. */ new_elts = 0; vec_foreach (e, elts) { if (e->user_data != user_data) vec_add1 (new_elts, e[0]); } vec_free (elts); return new_elts; } /* Insert user data on wheel at given CPU time stamp. */ void timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data) { /* Remove previously deleted elements. */ if (elt_is_deleted (w, user_data)) { timing_wheel_level_t *l; uword wi; /* Delete elts with given user data so that stale events don't expire. */ vec_foreach (l, w->levels) { /* *INDENT-OFF* */ clib_bitmap_foreach (wi, l->occupancy_bitmap, ({ l->elts[wi] = delete_user_data (l->elts[wi], user_data); if (vec_len (l->elts[wi]) == 0) l->occupancy_bitmap = clib_bitmap_andnoti (l->occupancy_bitmap, wi); })); /* *INDENT-ON* */ } { timing_wheel_overflow_elt_t *oe; /* *INDENT-OFF* */ pool_foreach (oe, w->overflow_pool, ({ if (oe->user_data == user_data) pool_put (w->overflow_pool, oe); })); /* *INDENT-ON* */ } hash_unset (w->deleted_user_data_hash, user_data); } timing_wheel_insert_helper (w, insert_cpu_time, user_data); } void timing_wheel_delete (timing_wheel_t * w, u32 user_data) { if (!w->deleted_user_data_hash) w->deleted_user_data_hash = hash_create ( /* capacity */ 0, /* value bytes */ 0); hash_set1 (w->deleted_user_data_hash, user_data); } /* Returns time of next expiring element. */ u64 timing_wheel_next_expiring_elt_time (timing_wheel_t * w) { timing_wheel_level_t *l; timing_wheel_elt_t *e; uword li, wi, wi0; u32 min_dt; u64 min_t; uword wrapped = 0; min_dt = ~0; min_t = ~0ULL; vec_foreach (l, w->levels) { if (!l->occupancy_bitmap) continue; li = l - w->levels; wi0 = wi = current_time_wheel_index (w, li); wrapped = 0; 
/*
 * Copyright (c) 2015 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
  Copyright (c) 2009 Eliot Dresselhaus

  Permission is hereby granted, free of charge, to any person obtaining
  a copy of this software and associated documentation files (the
  "Software"), to deal in the Software without restriction, including
  without limitation the rights to use, copy, modify, merge, publish,
  distribute, sublicense, and/or sell copies of the Software, and to
  permit persons to whom the Software is furnished to do so, subject to
  the following conditions:

  The above copyright notice and this permission notice shall be
  included in all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF