The timer-wheel Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The timer-wheel Reference Manual

This is the timer-wheel Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Aug 15 06:01:08 2022 GMT+0.

Table of Contents


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

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


2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 timer-wheel

A timer wheel implementation with BORDEAUX-THREADS backend.

Author

Nick Patrick <npatrick04@gmail.com>

License

MIT

Dependency

bordeaux-threads (system).

Source

timer-wheel.asd.

Child Component

src (module).


3 Modules

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


Previous: , Up: Modules   [Contents][Index]

3.1 timer-wheel/src

Source

timer-wheel.asd.

Parent Component

timer-wheel (system).

Child Components

4 Files

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


Previous: , Up: Files   [Contents][Index]

4.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

4.1.1 timer-wheel/timer-wheel.asd

Source

timer-wheel.asd.

Parent Component

timer-wheel (system).

ASDF Systems

timer-wheel.


4.1.2 timer-wheel/src/package.lisp

Source

timer-wheel.asd.

Parent Component

src (module).

Packages

timer-wheel.


4.1.3 timer-wheel/src/utils.lisp

Source

timer-wheel.asd.

Parent Component

src (module).

Internals

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

Source

timer-wheel.asd.

Parent Component

src (module).

Internals

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

Source

timer-wheel.asd.

Parent Component

src (module).

Public Interface
Internals

5 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

5.1 timer-wheel

Source

package.lisp.

Nickname

tw

Use List

common-lisp.

Public Interface
Internals

6 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Public Interface


Next: , Previous: , Up: Public Interface   [Contents][Index]

6.1.1 Special variables

Special Variable: *default-resolution*

milliseconds

Package

timer-wheel.

Source

timer-wheel.lisp.

Special Variable: *default-size*

slots per wheel

Package

timer-wheel.

Source

timer-wheel.lisp.


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.


6.1.3 Ordinary 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.

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.

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.

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.

Function: shutdown-timer-wheel (wheel)

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

Package

timer-wheel.

Source

timer-wheel.lisp.


6.1.4 Generic functions

Generic Reader: remaining (object)
Package

timer-wheel.

Methods
Reader Method: remaining ((timer timer))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

remaining.

Generic Writer: (setf remaining) (object)
Package

timer-wheel.

Methods
Writer Method: (setf remaining) ((timer timer))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

remaining.

Generic Function: uninstall-timer (wheel timer)

Remove TIMER from the WHEEL schedule.

Package

timer-wheel.

Source

timer-wheel.lisp.

Methods
Method: uninstall-timer ((wheel wheel) (timer timer))
Generic Reader: wheel-resolution (object)
Package

timer-wheel.

Methods
Reader Method: wheel-resolution ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

resolution.


6.1.5 Conditions

Condition: unscheduled
Package

timer-wheel.

Source

timer-wheel.lisp.

Direct superclasses

error.

Direct methods

unscheduled-timer.

Direct slots
Slot: timer
Initargs

:timer

Readers

unscheduled-timer.

Writers

This slot is read-only.


Previous: , Up: Public Interface   [Contents][Index]

6.1.6 Classes

Class: timer
Package

timer-wheel.

Source

timer-wheel.lisp.

Direct methods
Direct slots
Slot: remaining
Initform

(quote timer-wheel:unscheduled)

Initargs

:remaining

Readers

remaining.

Writers

(setf remaining).

Slot: installed-slot
Readers

installed-slot.

Writers

(setf installed-slot).

Slot: callback
Initargs

:callback

Readers

callback.

Writers

(setf callback).

Class: wheel
Package

timer-wheel.

Source

timer-wheel.lisp.

Direct methods
Direct slots
Slot: context
Initargs

:context

Readers

wheel-context.

Writers

(setf wheel-context).

Slot: timeout-lock
Initform

(bordeaux-threads:make-lock)

Readers

timeout-lock.

Writers

(setf timeout-lock).

Slot: thread
Initargs

:thread

Readers

wheel-thread.

Writers

(setf wheel-thread).

Slot: slots
Initargs

:slots

Readers

slots.

Writers

(setf slots).

Slot: current-slot
Initform

0

Readers

current-slot.

Writers

(setf current-slot).

Slot: resolution
Initform

timer-wheel:*default-resolution*

Initargs

:resolution

Readers

wheel-resolution.

Writers

This slot is read-only.

Slot: reset
Readers

reset.

Writers

(setf reset).


6.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

6.2.1 Constants

Constant: +milliseconds-per-second+
Package

timer-wheel.

Source

utils.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

6.2.2 Ordinary functions

Function: calculate-future-slot (current-slot remaining slots)
Package

timer-wheel.

Source

timer-wheel.lisp.

Function: current-milliseconds ()

Utility function to get the current time in milliseconds.

Package

timer-wheel.

Source

bt-timeout.lisp.

Function: initialize-timer (context resolution-milliseconds)

Called from the wheel thread.

Package

timer-wheel.

Source

bt-timeout.lisp.

Function: make-bt-context ()

Return a data structure for managing ticks with BORDEAUX-THREADS

Package

timer-wheel.

Source

bt-timeout.lisp.

Function: manage-timer-wheel (wheel)

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

Package

timer-wheel.

Source

timer-wheel.lisp.

Function: shutdown-context (context)
Package

timer-wheel.

Source

bt-timeout.lisp.

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.


Next: , Previous: , Up: Internals   [Contents][Index]

6.2.3 Generic functions

Generic Reader: callback (object)
Package

timer-wheel.

Methods
Reader Method: callback ((timer timer))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

callback.

Generic Writer: (setf callback) (object)
Package

timer-wheel.

Methods
Writer Method: (setf callback) ((timer timer))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

callback.

Generic Reader: context-end (object)
Package

timer-wheel.

Methods
Reader Method: context-end ((bt-timeout-context bt-timeout-context))

automatically generated reader method

Source

bt-timeout.lisp.

Target Slot

end.

Generic Writer: (setf context-end) (object)
Package

timer-wheel.

Methods
Writer Method: (setf context-end) ((bt-timeout-context bt-timeout-context))

automatically generated writer method

Source

bt-timeout.lisp.

Target Slot

end.

Generic Reader: context-resolution (object)
Package

timer-wheel.

Methods
Reader Method: context-resolution ((timeout-context timeout-context))

automatically generated reader method

Source

utils.lisp.

Target Slot

resolution.

Generic Writer: (setf context-resolution) (object)
Package

timer-wheel.

Methods
Writer Method: (setf context-resolution) ((timeout-context timeout-context))

automatically generated writer method

Source

utils.lisp.

Target Slot

resolution.

Generic Reader: current-slot (object)
Package

timer-wheel.

Methods
Reader Method: current-slot ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

current-slot.

Generic Writer: (setf current-slot) (object)
Package

timer-wheel.

Methods
Writer Method: (setf current-slot) ((wheel wheel))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

current-slot.

Generic Function: install-timer (wheel timer)

Add TIMER to the WHEEL schedule.

Package

timer-wheel.

Source

timer-wheel.lisp.

Methods
Method: install-timer ((wheel wheel) (timer timer))
Method: install-timer :before (wheel timer)
Generic Reader: installed-slot (object)
Package

timer-wheel.

Methods
Reader Method: installed-slot ((timer timer))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

installed-slot.

Generic Writer: (setf installed-slot) (object)
Package

timer-wheel.

Methods
Writer Method: (setf installed-slot) ((timer timer))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

installed-slot.

Generic Reader: reset (object)
Package

timer-wheel.

Methods
Reader Method: reset ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

reset.

Generic Writer: (setf reset) (object)
Package

timer-wheel.

Methods
Writer Method: (setf reset) ((wheel wheel))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

reset.

Generic Reader: slots (object)
Package

timer-wheel.

Methods
Reader Method: slots ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

slots.

Generic Writer: (setf slots) (object)
Package

timer-wheel.

Methods
Writer Method: (setf slots) ((wheel wheel))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

slots.

Generic Function: tick (wheel)

Operate one tick of the wheel scedule.

Package

timer-wheel.

Source

timer-wheel.lisp.

Methods
Method: tick ((wheel wheel))
Generic Reader: timeout-lock (object)
Package

timer-wheel.

Methods
Reader Method: timeout-lock ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

timeout-lock.

Generic Writer: (setf timeout-lock) (object)
Package

timer-wheel.

Methods
Writer Method: (setf timeout-lock) ((wheel wheel))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

timeout-lock.

Generic Reader: timeout-overrun (object)
Package

timer-wheel.

Methods
Reader Method: timeout-overrun ((timeout-context timeout-context))

automatically generated reader method

Source

utils.lisp.

Target Slot

timeout-overrun.

Generic Writer: (setf timeout-overrun) (object)
Package

timer-wheel.

Methods
Writer Method: (setf timeout-overrun) ((timeout-context timeout-context))

automatically generated writer method

Source

utils.lisp.

Target Slot

timeout-overrun.

Generic Reader: unscheduled-timer (condition)
Package

timer-wheel.

Methods
Reader Method: unscheduled-timer ((condition unscheduled))
Source

timer-wheel.lisp.

Target Slot

timer.

Generic Reader: wheel-context (object)
Package

timer-wheel.

Methods
Reader Method: wheel-context ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

context.

Generic Writer: (setf wheel-context) (object)
Package

timer-wheel.

Methods
Writer Method: (setf wheel-context) ((wheel wheel))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

context.

Generic Reader: wheel-thread (object)
Package

timer-wheel.

Methods
Reader Method: wheel-thread ((wheel wheel))

automatically generated reader method

Source

timer-wheel.lisp.

Target Slot

thread.

Generic Writer: (setf wheel-thread) (object)
Package

timer-wheel.

Methods
Writer Method: (setf wheel-thread) ((wheel wheel))

automatically generated writer method

Source

timer-wheel.lisp.

Target Slot

thread.


Previous: , Up: Internals   [Contents][Index]

6.2.4 Classes

Class: bt-timeout-context
Package

timer-wheel.

Source

bt-timeout.lisp.

Direct superclasses

timeout-context.

Direct methods
Direct slots
Slot: end
Readers

context-end.

Writers

(setf context-end).

Class: timeout-context
Package

timer-wheel.

Source

utils.lisp.

Direct subclasses

bt-timeout-context.

Direct methods
Direct slots
Slot: resolution
Initargs

:resolution

Readers

context-resolution.

Writers

(setf context-resolution).

Slot: timeout-overrun
Initform

0

Readers

timeout-overrun.

Writers

(setf timeout-overrun).


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
C   F   G   I   M   R   S   T   U   W  
Index Entry  Section

(
(setf callback): Private generic functions
(setf callback): Private generic functions
(setf context-end): Private generic functions
(setf context-end): Private generic functions
(setf context-resolution): Private generic functions
(setf context-resolution): Private generic functions
(setf current-slot): Private generic functions
(setf current-slot): Private generic functions
(setf installed-slot): Private generic functions
(setf installed-slot): Private generic functions
(setf remaining): Public generic functions
(setf remaining): Public generic functions
(setf reset): Private generic functions
(setf reset): Private generic functions
(setf slots): Private generic functions
(setf slots): Private generic functions
(setf timeout-lock): Private generic functions
(setf timeout-lock): Private generic functions
(setf timeout-overrun): Private generic functions
(setf timeout-overrun): Private generic functions
(setf wheel-context): Private generic functions
(setf wheel-context): Private generic functions
(setf wheel-thread): Private generic functions
(setf wheel-thread): Private generic functions

C
calculate-future-slot: Private ordinary functions
callback: Private generic functions
callback: Private generic functions
context-end: Private generic functions
context-end: Private generic functions
context-resolution: Private generic functions
context-resolution: Private generic functions
current-milliseconds: Private ordinary functions
current-slot: Private generic functions
current-slot: Private generic functions

F
Function, calculate-future-slot: Private ordinary functions
Function, current-milliseconds: Private ordinary functions
Function, initialize-timer: Private ordinary functions
Function, initialize-timer-wheel: Public ordinary functions
Function, make-bt-context: Private ordinary functions
Function, make-timer: Public ordinary functions
Function, make-wheel: Public ordinary functions
Function, manage-timer-wheel: Private ordinary functions
Function, schedule-timer: Public ordinary functions
Function, shutdown-context: Private ordinary functions
Function, shutdown-timer-wheel: Public ordinary functions
Function, wait-for-timeout: Private ordinary functions

G
Generic Function, (setf callback): Private generic functions
Generic Function, (setf context-end): Private generic functions
Generic Function, (setf context-resolution): Private generic functions
Generic Function, (setf current-slot): Private generic functions
Generic Function, (setf installed-slot): Private generic functions
Generic Function, (setf remaining): Public generic functions
Generic Function, (setf reset): Private generic functions
Generic Function, (setf slots): Private generic functions
Generic Function, (setf timeout-lock): Private generic functions
Generic Function, (setf timeout-overrun): Private generic functions
Generic Function, (setf wheel-context): Private generic functions
Generic Function, (setf wheel-thread): Private generic functions
Generic Function, callback: Private generic functions
Generic Function, context-end: Private generic functions
Generic Function, context-resolution: Private generic functions
Generic Function, current-slot: Private generic functions
Generic Function, install-timer: Private generic functions
Generic Function, installed-slot: Private generic functions
Generic Function, remaining: Public generic functions
Generic Function, reset: Private generic functions
Generic Function, slots: Private generic functions
Generic Function, tick: Private generic functions
Generic Function, timeout-lock: Private generic functions
Generic Function, timeout-overrun: Private generic functions
Generic Function, uninstall-timer: Public generic functions
Generic Function, unscheduled-timer: Private generic functions
Generic Function, wheel-context: Private generic functions
Generic Function, wheel-resolution: Public generic functions
Generic Function, wheel-thread: Private generic functions

I
initialize-timer: Private ordinary functions
initialize-timer-wheel: Public ordinary functions
install-timer: Private generic functions
install-timer: Private generic functions
install-timer: Private generic functions
installed-slot: Private generic functions
installed-slot: Private generic functions

M
Macro, with-timer-wheel: Public macros
make-bt-context: Private ordinary functions
make-timer: Public ordinary functions
make-wheel: Public ordinary functions
manage-timer-wheel: Private ordinary functions
Method, (setf callback): Private generic functions
Method, (setf context-end): Private generic functions
Method, (setf context-resolution): Private generic functions
Method, (setf current-slot): Private generic functions
Method, (setf installed-slot): Private generic functions
Method, (setf remaining): Public generic functions
Method, (setf reset): Private generic functions
Method, (setf slots): Private generic functions
Method, (setf timeout-lock): Private generic functions
Method, (setf timeout-overrun): Private generic functions
Method, (setf wheel-context): Private generic functions
Method, (setf wheel-thread): Private generic functions
Method, callback: Private generic functions
Method, context-end: Private generic functions
Method, context-resolution: Private generic functions
Method, current-slot: Private generic functions
Method, install-timer: Private generic functions
Method, install-timer: Private generic functions
Method, installed-slot: Private generic functions
Method, remaining: Public generic functions
Method, reset: Private generic functions
Method, slots: Private generic functions
Method, tick: Private generic functions
Method, timeout-lock: Private generic functions
Method, timeout-overrun: Private generic functions
Method, uninstall-timer: Public generic functions
Method, unscheduled-timer: Private generic functions
Method, wheel-context: Private generic functions
Method, wheel-resolution: Public generic functions
Method, wheel-thread: Private generic functions

R
remaining: Public generic functions
remaining: Public generic functions
reset: Private generic functions
reset: Private generic functions

S
schedule-timer: Public ordinary functions
shutdown-context: Private ordinary functions
shutdown-timer-wheel: Public ordinary functions
slots: Private generic functions
slots: Private generic functions

T
tick: Private generic functions
tick: Private generic functions
timeout-lock: Private generic functions
timeout-lock: Private generic functions
timeout-overrun: Private generic functions
timeout-overrun: Private generic functions

U
uninstall-timer: Public generic functions
uninstall-timer: Public generic functions
unscheduled-timer: Private generic functions
unscheduled-timer: Private generic functions

W
wait-for-timeout: Private ordinary functions
wheel-context: Private generic functions
wheel-context: Private generic functions
wheel-resolution: Public generic functions
wheel-resolution: Public generic functions
wheel-thread: Private generic functions
wheel-thread: Private generic functions
with-timer-wheel: Public macros

Jump to:   (  
C   F   G   I   M   R   S   T   U   W