2 * Copyright (c) 2011 Your File System Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
14 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
15 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
16 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
17 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
18 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
20 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
22 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 /* A reimplementation of the rx_event handler using red/black trees
27 * The first rx_event implementation used a simple sorted queue of all
28 * events, which lead to O(n^2) performance, where n is the number of
29 * outstanding events. This was found to scale poorly, so was replaced.
31 * The second implementation used a set of per-second buckets to store
32 * events. Each bucket (referred to as an epoch in the code) stored all
33 * of the events which expired in that second. However, on modern networks
34 * where RTT times are in the millisecond, most connections will have events
35 * expiring within the next second, so the problem reoccurs.
37 * This new implementation uses Red-Black trees to store a sorted list of
38 * events. Red Black trees are guaranteed to have no worse than O(log N)
39 * insertion, and are commonly used in timer applications
42 #include <afsconfig.h>
43 #include <afs/param.h>
46 # include "afs/sysincludes.h"
47 # include "afsincludes.h"
53 #include <opr/queue.h>
54 #include <opr/rbtree.h>
57 #include "rx_atomic.h"
59 #include "rx_globals.h"
63 struct opr_rbtree_node node;
64 struct clock eventTime;
68 void (*func)(struct rxevent *, void *, void *, int);
77 struct malloclist *next;
82 struct opr_queue list;
83 struct malloclist *mallocs;
88 struct opr_rbtree head;
89 struct rxevent *first;
100 static int allocUnit = 10;
102 static struct rxevent *
103 rxevent_alloc(void) {
104 struct rxevent *evlist;
106 struct malloclist *mrec;
109 MUTEX_ENTER(&freeEvents.lock);
110 if (opr_queue_IsEmpty(&freeEvents.list)) {
111 MUTEX_EXIT(&freeEvents.lock);
113 #if defined(AFS_AIX32_ENV) && defined(KERNEL)
114 ev = rxi_Alloc(sizeof(struct rxevent));
116 evlist = osi_Alloc(sizeof(struct rxevent) * allocUnit);
117 mrec = osi_Alloc(sizeof(struct malloclist));
120 mrec->size = sizeof(struct rxevent) * allocUnit;
122 MUTEX_ENTER(&freeEvents.lock);
123 for (i = 1; i < allocUnit; i++) {
124 opr_queue_Append(&freeEvents.list, &evlist[i].q);
126 mrec->next = freeEvents.mallocs;
127 freeEvents.mallocs = mrec;
128 MUTEX_EXIT(&freeEvents.lock);
132 ev = opr_queue_First(&freeEvents.list, struct rxevent, q);
133 opr_queue_Remove(&ev->q);
134 MUTEX_EXIT(&freeEvents.lock);
137 memset(ev, 0, sizeof(struct rxevent));
138 rx_atomic_set(&ev->refcnt, 1);
144 rxevent_free(struct rxevent *ev) {
145 MUTEX_ENTER(&freeEvents.lock);
146 opr_queue_Prepend(&freeEvents.list, &ev->q);
147 MUTEX_EXIT(&freeEvents.lock);
151 rxevent_put(struct rxevent *ev) {
152 if (rx_atomic_dec_and_read(&ev->refcnt) == 0) {
158 rxevent_Put(struct rxevent *ev) {
162 static_inline struct rxevent *
163 rxevent_get(struct rxevent *ev) {
164 rx_atomic_inc(&ev->refcnt);
169 rxevent_Get(struct rxevent *ev) {
170 return rxevent_get(ev);
173 /* Called if the time now is older than the last time we recorded running an
174 * event. This test catches machines where the system time has been set
175 * backwards, and avoids RX completely stalling when timers fail to fire.
177 * Take the different between now and the last event time, and subtract that
178 * from the timing of every event on the system. This does a relatively slow
179 * walk of the completely eventTree, but time-travel will hopefully be a pretty
182 * This can only safely be called from the event thread, as it plays with the
189 struct opr_rbtree_node *node;
190 struct clock adjTime, now;
192 MUTEX_ENTER(&eventTree.lock);
193 /* Time adjustment is expensive, make absolutely certain that we have
194 * to do it, by getting an up to date time to base our decision on
195 * once we've acquired the relevant locks.
198 if (!clock_Lt(&now, &eventSchedule.last))
201 adjTime = eventSchedule.last;
202 clock_Zero(&eventSchedule.last);
204 clock_Sub(&adjTime, &now);
206 /* If there are no events in the tree, then there's nothing to adjust */
207 if (eventTree.first == NULL)
210 node = opr_rbtree_first(&eventTree.head);
212 struct rxevent *event = opr_containerof(node, struct rxevent, node);
214 clock_Sub(&event->eventTime, &adjTime);
215 node = opr_rbtree_next(node);
217 eventSchedule.next = eventTree.first->eventTime;
220 MUTEX_EXIT(&eventTree.lock);
223 static int initialised = 0;
225 rxevent_Init(int nEvents, void (*scheduler)(void))
233 MUTEX_INIT(&eventTree.lock, "event tree lock", MUTEX_DEFAULT, 0);
234 opr_rbtree_init(&eventTree.head);
236 MUTEX_INIT(&freeEvents.lock, "free events lock", MUTEX_DEFAULT, 0);
237 opr_queue_Init(&freeEvents.list);
238 freeEvents.mallocs = NULL;
243 clock_Zero(&eventSchedule.next);
244 clock_Zero(&eventSchedule.last);
245 eventSchedule.raised = 0;
246 eventSchedule.func = scheduler;
250 rxevent_Post(struct clock *when, struct clock *now,
251 void (*func) (struct rxevent *, void *, void *, int),
252 void *arg, void *arg1, int arg2)
254 struct rxevent *ev, *event;
255 struct opr_rbtree_node **childptr, *parent = NULL;
257 ev = rxevent_alloc();
258 ev->eventTime = *when;
264 if (clock_Lt(now, &eventSchedule.last))
267 MUTEX_ENTER(&eventTree.lock);
269 /* Work out where in the tree we'll be storing this */
270 childptr = &eventTree.head.root;
273 event = opr_containerof((*childptr), struct rxevent, node);
276 if (clock_Lt(when, &event->eventTime))
277 childptr = &(*childptr)->left;
278 else if (clock_Gt(when, &event->eventTime))
279 childptr = &(*childptr)->right;
281 opr_queue_Append(&event->q, &ev->q);
285 opr_queue_Init(&ev->q);
286 opr_rbtree_insert(&eventTree.head, parent, childptr, &ev->node);
288 if (eventTree.first == NULL ||
289 clock_Lt(when, &(eventTree.first->eventTime))) {
290 eventTree.first = ev;
291 eventSchedule.raised = 1;
292 clock_Zero(&eventSchedule.next);
293 MUTEX_EXIT(&eventTree.lock);
294 if (eventSchedule.func != NULL)
295 (*eventSchedule.func)();
296 return rxevent_get(ev);
300 MUTEX_EXIT(&eventTree.lock);
301 return rxevent_get(ev);
304 /* We're going to remove ev from the tree, so set the first pointer to the
305 * next event after it */
307 resetFirst(struct rxevent *ev)
309 struct opr_rbtree_node *next = opr_rbtree_next(&ev->node);
311 eventTree.first = opr_containerof(next, struct rxevent, node);
313 eventTree.first = NULL;
317 rxevent_Cancel(struct rxevent **evp)
319 struct rxevent *event;
326 MUTEX_ENTER(&eventTree.lock);
328 if (!event->handled) {
329 /* We're a node on the red/black tree. If our list is non-empty,
330 * then swap the first element in the list in in our place,
331 * promoting it to the list head */
332 if (event->node.parent == NULL
333 && eventTree.head.root != &event->node) {
334 /* Not in the rbtree, therefore must be a list element */
335 opr_queue_Remove(&event->q);
337 if (!opr_queue_IsEmpty(&event->q)) {
338 struct rxevent *next;
340 next = opr_queue_First(&event->q, struct rxevent, q);
341 opr_queue_Remove(&next->q); /* Remove ourselves from list */
342 if (event->q.prev == &event->q) {
343 next->q.prev = next->q.next = &next->q;
346 next->q.prev->next = &next->q;
347 next->q.next->prev = &next->q;
350 opr_rbtree_replace(&eventTree.head, &event->node,
353 if (eventTree.first == event)
354 eventTree.first = next;
357 if (eventTree.first == event)
360 opr_rbtree_remove(&eventTree.head, &event->node);
364 rxevent_put(event); /* Dispose of eventTree reference */
367 MUTEX_EXIT(&eventTree.lock);
370 rxevent_put(event); /* Dispose of caller's reference */
373 /* Process all events which have expired. If events remain, then the relative
374 * time until the next event is returned in the parameter 'wait', and the
375 * function returns 1. If no events currently remain, the function returns 0
377 * If the current time is older than that of the last event processed, then we
378 * assume that time has gone backwards (for example, due to a system time reset)
379 * When this happens, all events in the current queue are rescheduled, using
380 * the difference between the current time and the last event time as a delta
384 rxevent_RaiseEvents(struct clock *wait)
387 struct rxevent *event;
392 /* Check for time going backwards */
393 if (clock_Lt(&now, &eventSchedule.last))
395 eventSchedule.last = now;
397 MUTEX_ENTER(&eventTree.lock);
398 /* Lock our event tree */
399 while (eventTree.first != NULL
400 && clock_Lt(&eventTree.first->eventTime, &now)) {
402 /* Grab the next node, either in the event's list, or in the tree node
403 * itself, and remove it from the event tree */
404 event = eventTree.first;
405 if (!opr_queue_IsEmpty(&event->q)) {
406 event = opr_queue_Last(&event->q, struct rxevent, q);
407 opr_queue_Remove(&event->q);
410 opr_rbtree_remove(&eventTree.head, &event->node);
413 MUTEX_EXIT(&eventTree.lock);
415 /* Fire the event, then free the structure */
416 event->func(event, event->arg, event->arg1, event->arg2);
419 MUTEX_ENTER(&eventTree.lock);
422 /* Figure out when we next need to be scheduled */
423 if (eventTree.first != NULL) {
424 *wait = eventSchedule.next = eventTree.first->eventTime;
425 ret = eventSchedule.raised = 1;
426 clock_Sub(wait, &now);
428 ret = eventSchedule.raised = 0;
431 MUTEX_EXIT(&eventTree.lock);
437 shutdown_rxevent(void)
439 struct malloclist *mrec, *nmrec;
444 MUTEX_DESTROY(&eventTree.lock);
446 #if !defined(AFS_AIX32_ENV) || !defined(KERNEL)
447 MUTEX_DESTROY(&freeEvents.lock);
448 mrec = freeEvents.mallocs;
451 osi_Free(mrec->mem, mrec->size);
452 osi_Free(mrec, sizeof(struct malloclist));