1 /******************************************************************************* 2 3 Manages ITimeoutClient instances where each one has an individual timeout 4 value. 5 6 To use the timeout manager, create a TimeoutManager subclass capable of 7 these two things: 8 1. It implements setTimeout() to set a timer that expires at the wall 9 clock time that is passed to setTimeout() as argument. 10 2. When the timer is expired, it calls checkTimeouts(). 11 12 Objects that can time out, the so-called timeout clients, must implement 13 ITimeoutClient. For each client create an ExpiryRegistration instance and 14 pass the object to the ExpiryRegistration constructor. 15 Call ExpiryRegistration.register() to set a timeout for the corresponding 16 client. When checkTimeouts() is called, it calls the timeout() method of 17 each timed out client. 18 19 20 Link with: 21 -Llibebtree.a 22 23 Build flags: 24 -debug=TimeoutManager = verbose output 25 26 Copyright: 27 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 28 All rights reserved. 29 30 License: 31 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 32 Alternatively, this file may be distributed under the terms of the Tango 33 3-Clause BSD License (see LICENSE_BSD.txt for details). 34 35 *******************************************************************************/ 36 37 module ocean.time.timeout.TimeoutManager; 38 39 40 import ocean.time.timeout.model.ITimeoutManager, 41 ocean.time.timeout.model.ITimeoutClient, 42 ocean.time.timeout.model.IExpiryRegistration, 43 ocean.time.timeout.model.ExpiryRegistrationBase; // ExpiryTree, Expiry, ExpiryRegistrationBase 44 45 import ocean.time.MicrosecondsClock; 46 47 import ocean.util.container.AppendBuffer; 48 49 50 import ocean.util.container.map.Map, 51 ocean.util.container.map.model.StandardHash, 52 ocean.util.container.map.model.IAllocator; 53 54 import ocean.meta.types.Qualifiers; 55 56 debug 57 { 58 import core.stdc.time: time_t, ctime; 59 import core.stdc.string: strlen; 60 } 61 62 /******************************************************************************* 63 64 Timeout manager 65 66 *******************************************************************************/ 67 68 class TimeoutManager : TimeoutManagerBase 69 { 70 /*************************************************************************** 71 72 Default expected number of elements in expiry registration to 73 ISelectClient map. 74 75 ***************************************************************************/ 76 77 private static immutable default_expected_no_elements = 1024; 78 79 /*************************************************************************** 80 81 Expiry registration class for an object that can time out. 82 83 ***************************************************************************/ 84 85 public class ExpiryRegistration : ExpiryRegistrationBase 86 { 87 /*********************************************************************** 88 89 Constructor 90 91 Params: 92 client = object that can time out 93 94 ***********************************************************************/ 95 96 public this ( ITimeoutClient client ) 97 { 98 super(this.outer..new TimeoutManagerInternal); 99 super.client = client; 100 } 101 102 /*********************************************************************** 103 104 Identifier string for debugging. 105 106 ***********************************************************************/ 107 108 debug public override cstring id ( ) 109 { 110 return super.client.id; 111 } 112 } 113 114 115 /*************************************************************************** 116 117 Constructor. 118 119 n = expected number of elements in expiry registration to 120 ISelectClient map 121 allocator = use this bucket element allocator for the expiry 122 registration to ISelectClient map. If it is null the default map 123 allocator (BucketElementGCAllocator) is used. 124 125 ***************************************************************************/ 126 127 public this ( size_t n = default_expected_no_elements, IAllocator allocator = null ) 128 { 129 super(n, allocator); 130 } 131 132 /*************************************************************************** 133 134 Constructor. 135 136 Params: 137 allocator = use this bucket element allocator for the expiry 138 registration to ISelectClient map. 139 140 ***************************************************************************/ 141 142 public this ( IAllocator allocator ) 143 { 144 super(default_expected_no_elements, allocator); 145 } 146 147 /*************************************************************************** 148 149 Creates a new expiry registration instance, associates client with it 150 and registers client with this timeout manager. 151 The returned object should be reused. The client will remain associated 152 to the expiry registration after it has been unregistered from the 153 timeout manager. 154 155 Params: 156 client = client to register 157 158 Returns: 159 new expiry registration object with client associated to. 160 161 ***************************************************************************/ 162 163 public IExpiryRegistration getRegistration ( ITimeoutClient client ) 164 { 165 return this.new ExpiryRegistration(client); 166 } 167 } 168 169 /******************************************************************************* 170 171 Timeout manager base class. Required for derivation because inside a 172 TimeoutManager subclass a nested ExpiryRegistration subclass is impossible. 173 174 *******************************************************************************/ 175 176 abstract class TimeoutManagerBase : ITimeoutManager 177 { 178 /*************************************************************************** 179 180 Enables IExpiryRegistration to access TimeoutManager internals. 181 182 ***************************************************************************/ 183 184 protected class TimeoutManagerInternal : ExpiryRegistrationBase.ITimeoutManagerInternal 185 { 186 /*********************************************************************** 187 188 Registers registration and sets the timeout for its client. 189 190 Params: 191 registration = IExpiryRegistration instance to register 192 timeout_us = timeout in microseconds from now 193 194 Returns: 195 expiry token: required for unregister(); the "key" member is the 196 wall clock time of expiration as UNIX time in microseconds. 197 198 ***********************************************************************/ 199 200 Expiry* register ( IExpiryRegistration registration, ulong timeout_us ) 201 { 202 return this.outer.register(registration, timeout_us); 203 } 204 205 /*********************************************************************** 206 207 Unregisters IExpiryRegistration instance corresponding to expiry. 208 209 Params: 210 expiry = expiry token returned by register() when registering 211 the IExpiryRegistration instance to unregister 212 213 In: 214 Must not be called from within timeout(). Doing so would still 215 leave already fired timer events in the TimeoutManager internal 216 list and their respective `timeout` will be called despite 217 unregistration. be called from within timeout(). 218 219 ***********************************************************************/ 220 221 void unregister ( ref Expiry expiry ) 222 { 223 this.outer.unregister(expiry); 224 } 225 226 /*********************************************************************** 227 228 If the expiry is present in the list of expired registrations being 229 currently iterated over by checkTimeouts, then it will be removed 230 (its timeout method will not be called). (This means that drop can 231 be called from timeout callbacks, unlike unregister.) 232 233 Does NOT unregister expiry, `this.unregister` has to be called 234 for that additionally. 235 236 Params: 237 registration = expiry registration reference 238 239 ***********************************************************************/ 240 241 protected void drop ( IExpiryRegistration registration ) 242 { 243 // If this method is called while checkTimeouts is iterating over 244 // the list of expired registrations, then we need to check whether 245 // the expiry to be dropped is present in the list and remove it, if 246 // it is. 247 // This makes it possible to disable timer events from the 248 // timeout callbacks of other timer events. 249 250 foreach (ref pending; this.outer.expired_registrations[]) 251 { 252 if (pending is registration) 253 pending = null; 254 } 255 } 256 257 /*********************************************************************** 258 259 Returns: 260 the current wall clock time as UNIX time in microseconds. 261 262 ***********************************************************************/ 263 264 ulong now ( ) 265 { 266 return this.outer.now(); 267 } 268 } 269 270 /*************************************************************************** 271 272 EBTree storing expiry time of registred clients in terms of microseconds 273 since the construction of this object (for direct comparison against 274 this.now_). 275 276 ***************************************************************************/ 277 278 private ExpiryTree expiry_tree; 279 280 281 /*************************************************************************** 282 283 Array map mapping from an expiry registration ( a node in the tree of 284 expiry times) to an ISelectClient. 285 286 ***************************************************************************/ 287 288 static class ExpiryToClient : Map!(IExpiryRegistration, Expiry*) 289 { 290 /*********************************************************************** 291 292 Constructor. 293 294 Params: 295 n = expected number of elements in mapping 296 allocator = use this bucket element allocator for the map. If it 297 is null the default allocator is used. 298 299 ***********************************************************************/ 300 301 public this ( size_t n, IAllocator allocator = null ) 302 { 303 // create the map with the default allocator 304 // BucketElementGCAllocator 305 if ( allocator is null ) 306 { 307 super(n); 308 } 309 else 310 { 311 super(allocator, n); 312 } 313 } 314 315 protected override hash_t toHash ( in Expiry* expiry ) 316 { 317 return StandardHash.fnv1aT(expiry); 318 } 319 } 320 321 322 private ExpiryToClient expiry_to_client; 323 324 /*************************************************************************** 325 326 List of expired registrations. Used by the checkTimeouts() method. 327 328 Elements can be set to `null` by `drop` method, in which case they 329 are ignored. 330 331 ***************************************************************************/ 332 333 private AppendBuffer!(IExpiryRegistration) expired_registrations; 334 335 /*************************************************************************** 336 337 Constructor. 338 339 n = expected number of elements in expiry registration to 340 ISelectClient map 341 allocator = use this bucket element allocator for the expiry 342 registration to ISelectClient map. If it is null the default 343 allocator (BucketElementGCAllocator) is used. 344 345 ***************************************************************************/ 346 347 protected this ( size_t n = 1024, IAllocator allocator = null ) 348 { 349 this.expiry_tree = new ExpiryTree; 350 this.expiry_to_client = new ExpiryToClient(n, allocator); 351 this.expired_registrations = new AppendBuffer!(IExpiryRegistration)(n); 352 } 353 354 355 /*************************************************************************** 356 357 Tells the wall clock time time when the next client will expire. 358 359 Returns: 360 the wall clock time when the next client will expire as UNIX time 361 in microseconds or ulong.max if no client is currently registered. 362 363 ***************************************************************************/ 364 365 public ulong next_expiration_us ( ) 366 { 367 Expiry* expiry = this.expiry_tree.first; 368 369 ulong us = expiry? expiry.key : ulong.max; 370 371 debug ( TimeoutManager ) if (!this.next_expiration_us_called_from_internal) 372 { 373 this.next_expiration_us_called_from_internal = false; 374 375 Stderr("next expiration: "); 376 377 if (us < us.max) 378 { 379 this.printTime(us); 380 } 381 else 382 { 383 Stderr("∞\n").flush(); 384 } 385 } 386 387 return us; 388 } 389 390 /*************************************************************************** 391 392 Tells the time left until the next client will expire. 393 394 Returns: 395 the time left until next client will expire in microseconds or 396 ulong.max if no client is currently registered. 0 indicates that 397 there are timed out clients that have not yet been notified and 398 unregistered. 399 400 ***************************************************************************/ 401 402 public ulong us_left ( ) 403 { 404 Expiry* expiry = this.expiry_tree.first; 405 406 if (expiry) 407 { 408 ulong next_expiration_us = expiry.key, 409 now = this.now; 410 411 debug ( TimeoutManager ) 412 { 413 ulong us = next_expiration_us > now? next_expiration_us - now : 0; 414 415 this.printTime(now, false); 416 Stderr(": ")(us)(" µs left\n").flush(); 417 418 return us; 419 } 420 else 421 { 422 return next_expiration_us > now? next_expiration_us - now : 0; 423 } 424 } 425 else 426 { 427 return ulong.max; 428 } 429 } 430 431 /*************************************************************************** 432 433 Returns: 434 the number of registered clients. 435 436 ***************************************************************************/ 437 438 public size_t pending ( ) 439 { 440 return this.expiry_tree.length; 441 } 442 443 /*************************************************************************** 444 445 Returns the current wall clock time according to gettimeofday(). 446 447 Returns: 448 the current wall clock time as UNIX time value in microseconds. 449 450 ***************************************************************************/ 451 452 public final ulong now ( ) 453 { 454 return MicrosecondsClock.now_us(); 455 } 456 457 /*************************************************************************** 458 459 Checks for timed out clients. For any timed out client its timeout() 460 method is called, then it is unregistered, finally dg() is called with 461 it as argument. 462 463 This method should be called when the timeout set by setTimeout() has 464 expired. 465 466 If dg returns false to cancel, the clients iterated over so far are 467 removed. To remove the remaining clients, call this method again. 468 469 Params: 470 dg = optional callback delegate that will be called with each timed 471 out client and must return true to continue or false to cancel. 472 473 Returns: 474 the number of expired clients. 475 476 ***************************************************************************/ 477 478 public size_t checkTimeouts ( scope bool delegate ( ITimeoutClient client ) dg = null ) 479 { 480 return this.checkTimeouts(this.now, dg); 481 } 482 483 public size_t checkTimeouts ( ulong now, scope bool delegate ( ITimeoutClient client ) dg = null ) 484 { 485 debug ( TimeoutManager ) 486 { 487 this.printTime(now, false); 488 Stderr(" --------------------- checkTimeouts\n"); 489 490 this.next_expiration_us_called_from_internal = true; 491 } 492 493 ulong previously_next = this.next_expiration_us; 494 495 this.expired_registrations.clear(); 496 497 // We first build up a list of all expired registrations, in order to 498 // avoid the situation of the timeout() delegates potentially modifying 499 // the tree while iterating over it. 500 501 version (all) 502 { 503 scope expiries = this.expiry_tree..new PartIterator(now); 504 505 foreach_reverse (ref expiry; expiries) 506 { 507 IExpiryRegistration registration = *this.expiry_to_client.get(&expiry); 508 509 debug ( TimeoutManager ) Stderr('\t')(registration.id)(" timed out\n"); 510 511 this.expired_registrations ~= registration; 512 } 513 } 514 else foreach (expiry, expire_time; this.expiry_tree.lessEqual(now)) 515 { 516 IExpiryRegistration registration = this.expiry_to_client[expiry]; 517 518 debug ( TimeoutManager ) Stderr('\t')(registration.id)(" timed out\n"); 519 520 this.expired_registrations ~= registration; 521 } 522 523 debug ( TimeoutManager ) Stderr.flush(); 524 525 // All expired registrations are removed from the expiry tree. They are 526 // removed before the timeout() delegates are called in order to avoid 527 // the situation of an expiry registration re-registering itself in its 528 // timeout() method, thus being registered in the expiry tree twice. 529 foreach (registration; this.expired_registrations[]) 530 { 531 registration.unregister(); 532 } 533 534 // Finally all expired registrations in the list are set to null and 535 // the timeout is updated. 536 scope ( exit ) 537 { 538 this.expired_registrations[] = cast(IExpiryRegistration)null; 539 540 this.setTimeout_(previously_next); 541 } 542 543 // The timeout() method of all expired registrations is called, until 544 // the optional delegate returns false. 545 foreach (ref registration; this.expired_registrations[]) 546 { 547 // registration can be disabled by `drop` method by being set to 548 // `null` 549 if (registration is null) 550 continue; 551 552 ITimeoutClient client = registration.timeout(); 553 554 if (dg !is null) if (!dg(client)) break; 555 } 556 557 return this.expired_registrations.length; 558 } 559 560 /*************************************************************************** 561 562 Registers registration and sets the timeout for its client. 563 564 Params: 565 registration = IExpiryRegistration instance to register 566 timeout_us = timeout in microseconds from now 567 568 Returns: 569 expiry token: required for unregister(); the "key" member is the 570 wall clock time of expiration as UNIX time in microseconds. 571 572 ***************************************************************************/ 573 574 protected Expiry* register ( IExpiryRegistration registration, ulong timeout_us ) 575 out (expiry) 576 { 577 assert (expiry); 578 } 579 do 580 { 581 ulong now = this.now; 582 583 ulong t = now + timeout_us; 584 585 debug ( TimeoutManager ) this.next_expiration_us_called_from_internal = true; 586 587 ulong previously_next = this.next_expiration_us; 588 589 Expiry* expiry = this.expiry_tree.add(t); 590 591 *this.expiry_to_client.put(expiry) = registration; 592 593 debug ( TimeoutManager ) 594 { 595 Stderr("----------- "); 596 this.printTime(now, false); 597 Stderr(" registered ")(registration.id)(" for ")(timeout_us)(" µs, times out at "); 598 this.printTime(t, false); 599 Stderr("\n\t")(this.expiry_tree.length)(" clients registered, first times out at "); 600 this.printTime(this.expiry_tree.first.key, false); 601 Stderr('\n'); 602 603 version (none) foreach (expiry, expire_time; this.expiry_tree.lessEqual(now + 20_000_000)) 604 { 605 IExpiryRegistration registration = this.expiry_to_client[expiry]; 606 607 Stderr('\t')('\t')(registration.id)(" "); 608 if ( expire_time <= now ) Stderr(" ** "); 609 this.printTime(expire_time); 610 } 611 } 612 613 this.setTimeout_(previously_next); 614 615 return expiry; 616 } 617 618 /*************************************************************************** 619 620 Unregisters the IExpiryRegistration instance corresponding to expiry. 621 622 Params: 623 expiry = expiry token returned by register() when registering the 624 IExpiryRegistration instance to unregister 625 626 Throws: 627 Exception if no IExpiryRegistration instance corresponding to expiry 628 is currently registered. 629 630 ***************************************************************************/ 631 632 protected void unregister ( ref Expiry expiry ) 633 { 634 debug ( TimeoutManager ) this.next_expiration_us_called_from_internal = true; 635 636 ulong previously_next = this.next_expiration_us; 637 638 debug ulong t = expiry.key; 639 640 try try 641 { 642 this.expiry_to_client.remove(&expiry); 643 } 644 finally 645 { 646 this.expiry_tree.remove(expiry); 647 } 648 finally 649 { 650 debug ( TimeoutManager ) 651 { 652 size_t n = this.expiry_tree.length; 653 654 Stderr("----------- "); 655 this.printTime(now, false); 656 Stderr(" unregistered "); 657 this.printTime(t, false); 658 Stderr("\n\t")(n)(" clients registered"); 659 if (n) 660 { 661 Stderr(", first times out at "); 662 this.printTime(this.expiry_tree.first.key, false); 663 } 664 Stderr('\n'); 665 } 666 667 this.setTimeout_(previously_next); 668 } 669 } 670 671 /*************************************************************************** 672 673 Called when the overall timeout needs to be set or changed. 674 675 Params: 676 next_expiration_us = wall clock time when the first client times 677 out so that checkTimeouts() must be called. 678 679 ***************************************************************************/ 680 681 protected void setTimeout ( ulong next_expiration_us ) { } 682 683 /*************************************************************************** 684 685 Called when the last client has been unregistered so that the timer may 686 be disabled. 687 688 ***************************************************************************/ 689 690 protected void stopTimeout ( ) { } 691 692 /*************************************************************************** 693 694 Calls setTimeout() or stopTimeout() if required. 695 696 Params: 697 previously_next = next expiration time before a client was 698 registered/unregistered 699 700 ***************************************************************************/ 701 702 private void setTimeout_ ( ulong previously_next ) 703 { 704 Expiry* expiry = this.expiry_tree.first; 705 706 if (expiry) 707 { 708 ulong next_now = expiry.key; 709 710 if (next_now != previously_next) 711 { 712 this.setTimeout(next_now); 713 } 714 } 715 else if (previously_next < previously_next.max) 716 { 717 this.stopTimeout(); 718 } 719 } 720 721 /*************************************************************************** 722 723 TODO: Remove debugging output. 724 725 ***************************************************************************/ 726 727 debug ( TimeoutManager ): 728 729 bool next_expiration_us_called_from_internal; 730 731 /*************************************************************************** 732 733 Prints the current wall clock time. 734 735 ***************************************************************************/ 736 737 void printTime ( bool nl = true ) 738 { 739 this.printTime(this.now, nl); 740 } 741 742 /*************************************************************************** 743 744 Prints t. 745 746 Params: 747 t = wall clock time as UNIX time in microseconds. 748 749 ***************************************************************************/ 750 751 static void printTime ( ulong t, bool nl = true ) 752 { 753 time_t s = cast (time_t) (t / 1_000_000); 754 uint us = cast (uint) (t % 1_000_000); 755 756 char* str = ctime(&s); 757 758 Stderr(str[0 .. strlen(str) - 1])('.')(us); 759 760 if (nl) Stderr('\n').flush(); 761 } 762 }