The timer-wheel Reference Manual

Table of Contents

The timer-wheel Reference Manual

This is the timer-wheel Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Mar 25 19:19:02 2020 GMT+0.

1 Introduction

Timer Wheel

A portable Common Lisp timer wheel implementation. A timer wheel provides an efficient mechanism to implement tick-based timer routines. The portable part of this is the backend using Boreaux Threads to run a background thread operating the wheel.

Note that this package uses the internal-real-time to manage inter-tick timing intervals. Thus the correctness of the interval depends on how the specific lisp implementation implements internal-real-time. For instance, SBCL currently uses gettimeofday internally which means that a leap-second can stop time.

References

For the original reference I used, see "Real-Time Embedded Systems" by Xiaocong Fan, chapter 22.3. For some background on timers in Linux

• http://www.elinux.org/Kernel_Timer_Systems
• https://lkml.org/lkml/2005/10/19/46.

Example

(asdf:load-system :timer-wheel.examples)

;; Increment and print a counter value every tick with two different counters.
;; A third counter triggers the completion of the test.
(tw.examples:test 100 1500)

Testing

I've tested on Windows with SBCL 1.3 and CCL 1.11. I could get a timer wheel running with a resolution of 20 milliseconds without overruns (Nothing else going on). If you start loading up the garbage collector, I'm guessing that you'll start getting overruns. Test to determine what works.

TODO

• Add a hierarchical timer wheel
• Add OS specific timer back-ends?
• HW timer backends?

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 timer-wheel

Author

Nick Patrick <npatrick04@gmail.com>

License

MIT

Description

A timer wheel implementation with BORDEAUX-THREADS backend.

Dependency

bordeaux-threads

Source

timer-wheel.asd (file)

Component

src (module)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 timer-wheel/src

Parent

timer-wheel (system)

Location

src/

Components

• package.lisp (file)
• utils.lisp (file)
• bt-timeout.lisp (file)
• timer-wheel.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 timer-wheel.asd

Location

timer-wheel.asd

Systems

timer-wheel (system)

4.1.2 timer-wheel/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

timer-wheel

4.1.3 timer-wheel/src/utils.lisp

Parent

src (module)

Location

src/utils.lisp

Internal Definitions

• +milliseconds-per-second+ (constant)
• context-resolution (method)
• (setf context-resolution) (method)
• timeout-context (class)
• timeout-overrun (method)
• (setf timeout-overrun) (method)

4.1.4 timer-wheel/src/bt-timeout.lisp

Parent

src (module)

Location

src/bt-timeout.lisp

Internal Definitions

• bt-timeout-context (class)
• context-end (method)
• (setf context-end) (method)
• current-milliseconds (function)
• initialize-timer (function)
• make-bt-context (function)
• shutdown-context (function)
• wait-for-timeout (function)

4.1.5 timer-wheel/src/timer-wheel.lisp

Parent

src (module)

Location

src/timer-wheel.lisp

Exported Definitions

• *default-resolution* (special variable)
• *default-size* (special variable)
• initialize-timer-wheel (function)
• make-timer (function)
• make-wheel (function)
• remaining (method)
• (setf remaining) (method)
• schedule-timer (function)
• shutdown-timer-wheel (function)
• timer (class)
• uninstall-timer (generic function)
• uninstall-timer (method)
• unscheduled (condition)
• wheel (class)
• wheel-resolution (method)
• with-timer-wheel (macro)

Internal Definitions

• calculate-future-slot (function)
• callback (method)
• (setf callback) (method)
• current-slot (method)
• (setf current-slot) (method)
• install-timer (generic function)
• install-timer (method)
• install-timer (method)
• installed-slot (method)
• (setf installed-slot) (method)
• manage-timer-wheel (function)
• reset (method)
• (setf reset) (method)
• slots (method)
• (setf slots) (method)
• tick (generic function)
• tick (method)
• timeout-lock (method)
• (setf timeout-lock) (method)
• unscheduled-timer (method)
• wheel-context (method)
• (setf wheel-context) (method)
• wheel-thread (method)
• (setf wheel-thread) (method)

5 Packages

Packages are listed by definition order.

5.1 timer-wheel

Source

package.lisp (file)

Nickname

tw

Use List

common-lisp

Exported Definitions

• *default-resolution* (special variable)
• *default-size* (special variable)
• initialize-timer-wheel (function)
• make-timer (function)
• make-wheel (function)
• remaining (generic function)
• remaining (method)
• (setf remaining) (method)
• (setf remaining) (generic function)
• schedule-timer (function)
• shutdown-timer-wheel (function)
• timer (class)
• uninstall-timer (generic function)
• uninstall-timer (method)
• unscheduled (condition)
• wheel (class)
• wheel-resolution (generic function)
• wheel-resolution (method)
• with-timer-wheel (macro)

Internal Definitions

• +milliseconds-per-second+ (constant)
• bt-timeout-context (class)
• calculate-future-slot (function)
• callback (generic function)
• callback (method)
• (setf callback) (method)
• (setf callback) (generic function)
• context-end (generic function)
• context-end (method)
• (setf context-end) (method)
• (setf context-end) (generic function)
• context-resolution (generic function)
• context-resolution (method)
• (setf context-resolution) (method)
• (setf context-resolution) (generic function)
• current-milliseconds (function)
• current-slot (generic function)
• current-slot (method)
• (setf current-slot) (method)
• (setf current-slot) (generic function)
• initialize-timer (function)
• install-timer (generic function)
• install-timer (method)
• install-timer (method)
• installed-slot (generic function)
• installed-slot (method)
• (setf installed-slot) (method)
• (setf installed-slot) (generic function)
• make-bt-context (function)
• manage-timer-wheel (function)
• reset (generic function)
• reset (method)
• (setf reset) (method)
• (setf reset) (generic function)
• shutdown-context (function)
• slots (generic function)
• slots (method)
• (setf slots) (method)
• (setf slots) (generic function)
• tick (generic function)
• tick (method)
• timeout-context (class)
• timeout-lock (generic function)
• timeout-lock (method)
• (setf timeout-lock) (method)
• (setf timeout-lock) (generic function)
• timeout-overrun (generic function)
• timeout-overrun (method)
• (setf timeout-overrun) (method)
• (setf timeout-overrun) (generic function)
• unscheduled-timer (generic function)
• unscheduled-timer (method)
• wait-for-timeout (function)
• wheel-context (generic function)
• wheel-context (method)
• (setf wheel-context) (method)
• (setf wheel-context) (generic function)
• wheel-thread (generic function)
• wheel-thread (method)
• (setf wheel-thread) (method)
• (setf wheel-thread) (generic function)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Special variables

Special Variable: *default-resolution*

milliseconds

Package

timer-wheel

Source

timer-wheel.lisp (file)

Special Variable: *default-size*

slots per wheel

Package

timer-wheel

Source

timer-wheel.lisp (file)

6.1.2 Macros

Macro: with-timer-wheel WHEEL &body BODY

Execute BODY after initializing WHEEL, then
clean up by shutting WHEEL down after leaving the scope.

Package

timer-wheel

Source

timer-wheel.lisp (file)

6.1.3 Functions

Function: initialize-timer-wheel WHEEL

Ensure the WHEEL is stopped, then initialize the WHEEL context, and start the WHEEL thread.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Function: make-timer CALLBACK

Return a timer object with CALLBACK being
a function that accepts WHEEL and TIMER arguments.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Function: make-wheel &optional SIZE RESOLUTION BACKEND

Make a timer wheel with SIZE slots, with a millisecond RESOLUTION, and BACKEND of :BT (bordeaux-threads... the only backend).

Package

timer-wheel

Source

timer-wheel.lisp (file)

Function: schedule-timer WHEEL TIMER &key TICKS MILLISECONDS SECONDS

Schedule a timer with one of
:ticks - The number of resolution steps per (wheel-resolution wheel), minimum of 1 tick.
:milliseconds - The integer number of milliseconds worth of ticks, must be (and (plusp milliseconds)
(zerop (mod milliseconds (wheel-resolution wheel)))). :seconds - The real value of seconds, rounded to the nearest resolution tick.

In all cases, the timeout will elapse in no more than
(* calculated-quantity-of-ticks resolution) milliseconds.

The keyword arguments are checked in this order: ticks, milliseconds, seconds for valid values.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Function: shutdown-timer-wheel WHEEL

Notify the wheel thread to terminate, then wait for it.

Package

timer-wheel

Source

timer-wheel.lisp (file)

6.1.4 Generic functions

Generic Function: remaining OBJECT

Generic Function: (setf remaining) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: remaining (TIMER timer)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf remaining) NEW-VALUE (TIMER timer)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: uninstall-timer WHEEL TIMER

Remove TIMER from the WHEEL schedule.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Methods

Method: uninstall-timer (WHEEL wheel) (TIMER timer)

Generic Function: wheel-resolution OBJECT

Package

timer-wheel

Methods

Method: wheel-resolution (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

6.1.5 Conditions

Condition: unscheduled ()

Package

timer-wheel

Source

timer-wheel.lisp (file)

Direct superclasses

error (condition)

Direct methods

unscheduled-timer (method)

Direct slots

Slot: timer

Initargs

:timer

Readers

unscheduled-timer (generic function)

6.1.6 Classes

Class: timer ()

Package

timer-wheel

Source

timer-wheel.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• uninstall-timer (method)
• install-timer (method)
• callback (method)
• callback (method)
• installed-slot (method)
• installed-slot (method)
• remaining (method)
• remaining (method)

Direct slots

Slot: remaining

Initargs

:remaining

Initform

(quote timer-wheel:unscheduled)

Readers

remaining (generic function)

Writers

(setf remaining) (generic function)

Slot: installed-slot

Readers

installed-slot (generic function)

Writers

(setf installed-slot) (generic function)

Slot: callback

Initargs

:callback

Readers

callback (generic function)

Writers

(setf callback) (generic function)

Class: wheel ()

Package

timer-wheel

Source

timer-wheel.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• uninstall-timer (method)
• install-timer (method)
• tick (method)
• reset (method)
• reset (method)
• wheel-resolution (method)
• current-slot (method)
• current-slot (method)
• slots (method)
• slots (method)
• wheel-thread (method)
• wheel-thread (method)
• timeout-lock (method)
• timeout-lock (method)
• wheel-context (method)
• wheel-context (method)

Direct slots

Slot: context

Initargs

:context

Readers

wheel-context (generic function)

Writers

(setf wheel-context) (generic function)

Slot: timeout-lock

Initform

(bordeaux-threads:make-lock)

Readers

timeout-lock (generic function)

Writers

(setf timeout-lock) (generic function)

Slot: thread

Initargs

:thread

Readers

wheel-thread (generic function)

Writers

(setf wheel-thread) (generic function)

Slot: slots

Initargs

:slots

Readers

slots (generic function)

Writers

(setf slots) (generic function)

Slot: current-slot

Initform

0

Readers

current-slot (generic function)

Writers

(setf current-slot) (generic function)

Slot: resolution

Initargs

:resolution

Initform

timer-wheel:*default-resolution*

Readers

wheel-resolution (generic function)

Slot: reset

Readers

reset (generic function)

Writers

(setf reset) (generic function)

6.2 Internal definitions

6.2.1 Constants

Constant: +milliseconds-per-second+

Package

timer-wheel

Source

utils.lisp (file)

6.2.2 Functions

Function: calculate-future-slot CURRENT-SLOT REMAINING SLOTS

Package

timer-wheel

Source

timer-wheel.lisp (file)

Function: current-milliseconds ()

Utility function to get the current time in milliseconds.

Package

timer-wheel

Source

bt-timeout.lisp (file)

Function: initialize-timer CONTEXT RESOLUTION-MILLISECONDS

Called from the wheel thread.

Package

timer-wheel

Source

bt-timeout.lisp (file)

Function: make-bt-context ()

Return a data structure for managing ticks with BORDEAUX-THREADS

Package

timer-wheel

Source

bt-timeout.lisp (file)

Function: manage-timer-wheel WHEEL

This is the main entry point of the timer WHEEL thread.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Function: shutdown-context CONTEXT

Package

timer-wheel

Source

bt-timeout.lisp (file)

Function: wait-for-timeout CONTEXT

This thread maintains a continually updating real-time that it is targetting for precise sleeps. If a sleep cannot be done to reach the target time...i.e. we’ve missed the time getting to this thread, then increment the *timeout-overrun* counter, and keep going as though all was well. I cannot think of any specific failure behavior that would be generically ok.

Package

timer-wheel

Source

bt-timeout.lisp (file)

6.2.3 Generic functions

Generic Function: callback OBJECT

Generic Function: (setf callback) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: callback (TIMER timer)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf callback) NEW-VALUE (TIMER timer)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: context-end OBJECT

Generic Function: (setf context-end) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: context-end (BT-TIMEOUT-CONTEXT bt-timeout-context)

automatically generated reader method

Source

bt-timeout.lisp (file)

Method: (setf context-end) NEW-VALUE (BT-TIMEOUT-CONTEXT bt-timeout-context)

automatically generated writer method

Source

bt-timeout.lisp (file)

Generic Function: context-resolution OBJECT

Generic Function: (setf context-resolution) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: context-resolution (TIMEOUT-CONTEXT timeout-context)

automatically generated reader method

Source

utils.lisp (file)

Method: (setf context-resolution) NEW-VALUE (TIMEOUT-CONTEXT timeout-context)

automatically generated writer method

Source

utils.lisp (file)

Generic Function: current-slot OBJECT

Generic Function: (setf current-slot) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: current-slot (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf current-slot) NEW-VALUE (WHEEL wheel)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: install-timer WHEEL TIMER

Add TIMER to the WHEEL schedule.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Methods

Method: install-timer (WHEEL wheel) (TIMER timer)

Method: install-timer WHEEL TIMER before

Generic Function: installed-slot OBJECT

Generic Function: (setf installed-slot) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: installed-slot (TIMER timer)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf installed-slot) NEW-VALUE (TIMER timer)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: reset OBJECT

Generic Function: (setf reset) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: reset (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf reset) NEW-VALUE (WHEEL wheel)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: slots OBJECT

Generic Function: (setf slots) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: slots (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf slots) NEW-VALUE (WHEEL wheel)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: tick WHEEL

Operate one tick of the wheel scedule.

Package

timer-wheel

Source

timer-wheel.lisp (file)

Methods

Method: tick (WHEEL wheel)

Generic Function: timeout-lock OBJECT

Generic Function: (setf timeout-lock) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: timeout-lock (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf timeout-lock) NEW-VALUE (WHEEL wheel)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: timeout-overrun OBJECT

Generic Function: (setf timeout-overrun) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: timeout-overrun (TIMEOUT-CONTEXT timeout-context)

automatically generated reader method

Source

utils.lisp (file)

Method: (setf timeout-overrun) NEW-VALUE (TIMEOUT-CONTEXT timeout-context)

automatically generated writer method

Source

utils.lisp (file)

Generic Function: unscheduled-timer CONDITION

Package

timer-wheel

Methods

Method: unscheduled-timer (CONDITION unscheduled)

Source

timer-wheel.lisp (file)

Generic Function: wheel-context OBJECT

Generic Function: (setf wheel-context) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: wheel-context (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf wheel-context) NEW-VALUE (WHEEL wheel)

automatically generated writer method

Source

timer-wheel.lisp (file)

Generic Function: wheel-thread OBJECT

Generic Function: (setf wheel-thread) NEW-VALUE OBJECT

Package

timer-wheel

Methods

Method: wheel-thread (WHEEL wheel)

automatically generated reader method

Source

timer-wheel.lisp (file)

Method: (setf wheel-thread) NEW-VALUE (WHEEL wheel)

automatically generated writer method

Source

timer-wheel.lisp (file)

6.2.4 Classes

Class: bt-timeout-context ()

Package

timer-wheel

Source

bt-timeout.lisp (file)

Direct superclasses

timeout-context (class)

Direct methods

• context-end (method)
• context-end (method)

Direct slots

Slot: end

Readers

context-end (generic function)

Writers

(setf context-end) (generic function)

Class: timeout-context ()

Package

timer-wheel

Source

utils.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

bt-timeout-context (class)

Direct methods

• timeout-overrun (method)
• timeout-overrun (method)
• context-resolution (method)
• context-resolution (method)

Direct slots

Slot: resolution

Initargs

:resolution

Readers

context-resolution (generic function)

Writers

(setf context-resolution) (generic function)

Slot: timeout-overrun

Initform

0

Readers

timeout-overrun (generic function)

Writers

(setf timeout-overrun) (generic function)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types