sys/dev/sound/clone.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2007 Ariff Abdullah <ariff@FreeBSD.org>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  * $FreeBSD$
  29  */
  30
  31 #include <sys/param.h>
  32 #include <sys/systm.h>
  33 #include <sys/conf.h>
  34 #include <sys/kernel.h>
  35 #include <sys/malloc.h>
  36 #include <sys/proc.h>
  37
  38 #ifdef HAVE_KERNEL_OPTION_HEADERS
  39 #include "opt_snd.h"
  40 #endif
  41
  42 #if defined(SND_DIAGNOSTIC) || defined(SND_DEBUG)
  43 #include <dev/sound/pcm/sound.h>
  44 #endif
  45
  46 #include <dev/sound/clone.h>
  47
  48 /*
  49  * So here we go again, another clonedevs manager. Unlike default clonedevs,
  50  * this clone manager is designed to withstand various abusive behavior
  51  * (such as 'while : ; do ls /dev/whatever ; done', etc.), reusable object
  52  * after reaching certain expiration threshold, aggressive garbage collector,
  53  * transparent device allocator and concurrency handling across multiple
  54  * thread/proc. Due to limited information given by dev_clone EVENTHANDLER,
  55  * we don't have much clues whether the caller wants a real open() or simply
  56  * making fun of us with things like stat(), mtime() etc. Assuming that:
  57  * 1) Time window between dev_clone EH <-> real open() should be small
  58  * enough and 2) mtime()/stat() etc. always looks like a half way / stalled
  59  * operation, we can decide whether a new cdev must be created, old
  60  * (expired) cdev can be reused or an existing cdev can be shared.
  61  *
  62  * Most of the operations and logics are generic enough and can be applied
  63  * on other places (such as if_tap, snp, etc).  Perhaps this can be
  64  * rearranged to complement clone_*(). However, due to this still being
  65  * specific to the sound driver (and as a proof of concept on how it can be
  66  * done), si_drv2 is used to keep the pointer of the clone list entry to
  67  * avoid expensive lookup.
  68  */
  69
  70 /* clone entry */
  71 struct snd_clone_entry {
  72         TAILQ_ENTRY(snd_clone_entry) link;
  73         struct snd_clone *parent;
  74         struct cdev *devt;
  75         struct timespec tsp;
  76         uint32_t flags;
  77         pid_t pid;
  78         int unit;
  79 };
  80
  81 /* clone manager */
  82 struct snd_clone {
  83         TAILQ_HEAD(link_head, snd_clone_entry) head;
  84         struct timespec tsp;
  85         int refcount;
  86         int size;
  87         int typemask;
  88         int maxunit;
  89         int deadline;
  90         uint32_t flags;
  91 };
  92
  93 #ifdef SND_DIAGNOSTIC
  94 #define SND_CLONE_ASSERT(x, y)          do {                    \
  95         if (!(x))                                               \
  96                 panic y;                                        \
  97 } while (0)
  98 #else
  99 #define SND_CLONE_ASSERT(...)           KASSERT(__VA_ARGS__)
 100 #endif
 101
 102 /*
 103  * Shamelessly ripped off from vfs_subr.c
 104  * We need at least 1/HZ precision as default timestamping.
 105  */
 106 enum { SND_TSP_SEC, SND_TSP_HZ, SND_TSP_USEC, SND_TSP_NSEC };
 107
 108 static int snd_timestamp_precision = SND_TSP_HZ;
 109 TUNABLE_INT("hw.snd.timestamp_precision", &snd_timestamp_precision);
 110
 111 void
 112 snd_timestamp(struct timespec *tsp)
 113 {
 114         struct timeval tv;
 115
 116         switch (snd_timestamp_precision) {
 117         case SND_TSP_SEC:
 118                 tsp->tv_sec = time_second;
 119                 tsp->tv_nsec = 0;
 120                 break;
 121         case SND_TSP_HZ:
 122                 getnanouptime(tsp);
 123                 break;
 124         case SND_TSP_USEC:
 125                 microuptime(&tv);
 126                 TIMEVAL_TO_TIMESPEC(&tv, tsp);
 127                 break;
 128         case SND_TSP_NSEC:
 129                 nanouptime(tsp);
 130                 break;
 131         default:
 132                 snd_timestamp_precision = SND_TSP_HZ;
 133                 getnanouptime(tsp);
 134                 break;
 135         }
 136 }
 137
 138 #if defined(SND_DIAGNOSTIC) || defined(SND_DEBUG)
 139 static int
 140 sysctl_hw_snd_timestamp_precision(SYSCTL_HANDLER_ARGS)
 141 {
 142         int err, val;
 143
 144         val = snd_timestamp_precision;
 145         err = sysctl_handle_int(oidp, &val, 0, req);
 146         if (err == 0 && req->newptr != NULL) {
 147                 switch (val) {
 148                 case SND_TSP_SEC:
 149                 case SND_TSP_HZ:
 150                 case SND_TSP_USEC:
 151                 case SND_TSP_NSEC:
 152                         snd_timestamp_precision = val;
 153                         break;
 154                 default:
 155                         break;
 156                 }
 157         }
 158
 159         return (err);
 160 }
 161 SYSCTL_PROC(_hw_snd, OID_AUTO, timestamp_precision,
 162     CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 0, sizeof(int),
 163     sysctl_hw_snd_timestamp_precision, "I",
 164     "timestamp precision (0=s 1=hz 2=us 3=ns)");
 165 #endif
 166
 167 /*
 168  * snd_clone_create() : Return opaque allocated clone manager.
 169  */
 170 struct snd_clone *
 171 snd_clone_create(int typemask, int maxunit, int deadline, uint32_t flags)
 172 {
 173         struct snd_clone *c;
 174
 175         SND_CLONE_ASSERT(!(typemask & ~SND_CLONE_MAXUNIT),
 176             ("invalid typemask: 0x%08x", typemask));
 177         SND_CLONE_ASSERT(maxunit == -1 ||
 178             !(maxunit & ~(~typemask & SND_CLONE_MAXUNIT)),
 179             ("maxunit overflow: typemask=0x%08x maxunit=%d",
 180             typemask, maxunit));
 181         SND_CLONE_ASSERT(!(flags & ~SND_CLONE_MASK),
 182             ("invalid clone flags=0x%08x", flags));
 183
 184         c = malloc(sizeof(*c), M_DEVBUF, M_WAITOK | M_ZERO);
 185         c->refcount = 0;
 186         c->size = 0;
 187         c->typemask = typemask;
 188         c->maxunit = (maxunit == -1) ? (~typemask & SND_CLONE_MAXUNIT) :
 189             maxunit;
 190         c->deadline = deadline;
 191         c->flags = flags;
 192         snd_timestamp(&c->tsp);
 193         TAILQ_INIT(&c->head);
 194
 195         return (c);
 196 }
 197
 198 int
 199 snd_clone_busy(struct snd_clone *c)
 200 {
 201         struct snd_clone_entry *ce;
 202
 203         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 204
 205         if (c->size == 0)
 206                 return (0);
 207
 208         TAILQ_FOREACH(ce, &c->head, link) {
 209                 if ((ce->flags & SND_CLONE_BUSY) ||
 210                     (ce->devt != NULL && ce->devt->si_threadcount != 0))
 211                         return (EBUSY);
 212         }
 213
 214         return (0);
 215 }
 216
 217 /*
 218  * snd_clone_enable()/disable() : Suspend/resume clone allocation through
 219  * snd_clone_alloc(). Everything else will not be affected by this.
 220  */
 221 int
 222 snd_clone_enable(struct snd_clone *c)
 223 {
 224         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 225
 226         if (c->flags & SND_CLONE_ENABLE)
 227                 return (EINVAL);
 228
 229         c->flags |= SND_CLONE_ENABLE;
 230
 231         return (0);
 232 }
 233
 234 int
 235 snd_clone_disable(struct snd_clone *c)
 236 {
 237         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 238
 239         if (!(c->flags & SND_CLONE_ENABLE))
 240                 return (EINVAL);
 241
 242         c->flags &= ~SND_CLONE_ENABLE;
 243
 244         return (0);
 245 }
 246
 247 /*
 248  * Getters / Setters. Not worth explaining :)
 249  */
 250 int
 251 snd_clone_getsize(struct snd_clone *c)
 252 {
 253         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 254
 255         return (c->size);
 256 }
 257
 258 int
 259 snd_clone_getmaxunit(struct snd_clone *c)
 260 {
 261         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 262
 263         return (c->maxunit);
 264 }
 265
 266 int
 267 snd_clone_setmaxunit(struct snd_clone *c, int maxunit)
 268 {
 269         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 270         SND_CLONE_ASSERT(maxunit == -1 ||
 271             !(maxunit & ~(~c->typemask & SND_CLONE_MAXUNIT)),
 272             ("maxunit overflow: typemask=0x%08x maxunit=%d",
 273             c->typemask, maxunit));
 274
 275         c->maxunit = (maxunit == -1) ? (~c->typemask & SND_CLONE_MAXUNIT) :
 276             maxunit;
 277
 278         return (c->maxunit);
 279 }
 280
 281 int
 282 snd_clone_getdeadline(struct snd_clone *c)
 283 {
 284         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 285
 286         return (c->deadline);
 287 }
 288
 289 int
 290 snd_clone_setdeadline(struct snd_clone *c, int deadline)
 291 {
 292         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 293
 294         c->deadline = deadline;
 295
 296         return (c->deadline);
 297 }
 298
 299 int
 300 snd_clone_gettime(struct snd_clone *c, struct timespec *tsp)
 301 {
 302         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 303         SND_CLONE_ASSERT(tsp != NULL, ("NULL timespec"));
 304
 305         *tsp = c->tsp;
 306
 307         return (0);
 308 }
 309
 310 uint32_t
 311 snd_clone_getflags(struct snd_clone *c)
 312 {
 313         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 314
 315         return (c->flags);
 316 }
 317
 318 uint32_t
 319 snd_clone_setflags(struct snd_clone *c, uint32_t flags)
 320 {
 321         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 322         SND_CLONE_ASSERT(!(flags & ~SND_CLONE_MASK),
 323             ("invalid clone flags=0x%08x", flags));
 324
 325         c->flags = flags;
 326
 327         return (c->flags);
 328 }
 329
 330 int
 331 snd_clone_getdevtime(struct cdev *dev, struct timespec *tsp)
 332 {
 333         struct snd_clone_entry *ce;
 334
 335         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 336         SND_CLONE_ASSERT(tsp != NULL, ("NULL timespec"));
 337
 338         ce = dev->si_drv2;
 339         if (ce == NULL)
 340                 return (ENODEV);
 341
 342         SND_CLONE_ASSERT(ce->parent != NULL, ("NULL parent"));
 343
 344         *tsp = ce->tsp;
 345
 346         return (0);
 347 }
 348
 349 uint32_t
 350 snd_clone_getdevflags(struct cdev *dev)
 351 {
 352         struct snd_clone_entry *ce;
 353
 354         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 355
 356         ce = dev->si_drv2;
 357         if (ce == NULL)
 358                 return (0xffffffff);
 359
 360         SND_CLONE_ASSERT(ce->parent != NULL, ("NULL parent"));
 361
 362         return (ce->flags);
 363 }
 364
 365 uint32_t
 366 snd_clone_setdevflags(struct cdev *dev, uint32_t flags)
 367 {
 368         struct snd_clone_entry *ce;
 369
 370         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 371         SND_CLONE_ASSERT(!(flags & ~SND_CLONE_DEVMASK),
 372             ("invalid clone dev flags=0x%08x", flags));
 373
 374         ce = dev->si_drv2;
 375         if (ce == NULL)
 376                 return (0xffffffff);
 377
 378         SND_CLONE_ASSERT(ce->parent != NULL, ("NULL parent"));
 379
 380         ce->flags = flags;
 381
 382         return (ce->flags);
 383 }
 384
 385 /* Elapsed time conversion to ms */
 386 #define SND_CLONE_ELAPSED(x, y)                                         \
 387         ((((x)->tv_sec - (y)->tv_sec) * 1000) +                         \
 388         (((y)->tv_nsec > (x)->tv_nsec) ?                                \
 389         (((1000000000L + (x)->tv_nsec -                                 \
 390         (y)->tv_nsec) / 1000000) - 1000) :                              \
 391         (((x)->tv_nsec - (y)->tv_nsec) / 1000000)))
 392
 393 #define SND_CLONE_EXPIRED(x, y, z)                                      \
 394         ((x)->deadline < 1 ||                                           \
 395         ((y)->tv_sec - (z)->tv_sec) > ((x)->deadline / 1000) ||         \
 396         SND_CLONE_ELAPSED(y, z) > (x)->deadline)
 397
 398 /*
 399  * snd_clone_gc() : Garbage collector for stalled, expired objects. Refer to
 400  * clone.h for explanations on GC settings.
 401  */
 402 int
 403 snd_clone_gc(struct snd_clone *c)
 404 {
 405         struct snd_clone_entry *ce, *tce;
 406         struct timespec now;
 407         int pruned;
 408
 409         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 410
 411         if (!(c->flags & SND_CLONE_GC_ENABLE) || c->size == 0)
 412                 return (0);
 413
 414         snd_timestamp(&now);
 415
 416         /*
 417          * Bail out if the last clone handler was invoked below the deadline
 418          * threshold.
 419          */
 420         if ((c->flags & SND_CLONE_GC_EXPIRED) &&
 421             !SND_CLONE_EXPIRED(c, &now, &c->tsp))
 422                 return (0);
 423
 424         pruned = 0;
 425
 426         /*
 427          * Visit each object in reverse order. If the object is still being
 428          * referenced by a valid open(), skip it. Look for expired objects
 429          * and either revoke its clone invocation status or mercilessly
 430          * throw it away.
 431          */
 432         TAILQ_FOREACH_REVERSE_SAFE(ce, &c->head, link_head, link, tce) {
 433                 if (!(ce->flags & SND_CLONE_BUSY) &&
 434                     (!(ce->flags & SND_CLONE_INVOKE) ||
 435                     SND_CLONE_EXPIRED(c, &now, &ce->tsp))) {
 436                         if ((c->flags & SND_CLONE_GC_REVOKE) ||
 437                             ce->devt->si_threadcount != 0) {
 438                                 ce->flags &= ~SND_CLONE_INVOKE;
 439                                 ce->pid = -1;
 440                         } else {
 441                                 TAILQ_REMOVE(&c->head, ce, link);
 442                                 destroy_dev(ce->devt);
 443                                 free(ce, M_DEVBUF);
 444                                 c->size--;
 445                         }
 446                         pruned++;
 447                 }
 448         }
 449
 450         /* return total pruned objects */
 451         return (pruned);
 452 }
 453
 454 void
 455 snd_clone_destroy(struct snd_clone *c)
 456 {
 457         struct snd_clone_entry *ce, *tmp;
 458
 459         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 460
 461         ce = TAILQ_FIRST(&c->head);
 462         while (ce != NULL) {
 463                 tmp = TAILQ_NEXT(ce, link);
 464                 if (ce->devt != NULL)
 465                         destroy_dev(ce->devt);
 466                 free(ce, M_DEVBUF);
 467                 ce = tmp;
 468         }
 469
 470         free(c, M_DEVBUF);
 471 }
 472
 473 /*
 474  * snd_clone_acquire() : The vital part of concurrency management. Must be
 475  * called somewhere at the beginning of open() handler. ENODEV is not really
 476  * fatal since it just tell the caller that this is not cloned stuff.
 477  * EBUSY is *real*, don't forget that!
 478  */
 479 int
 480 snd_clone_acquire(struct cdev *dev)
 481 {
 482         struct snd_clone_entry *ce;
 483
 484         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 485
 486         ce = dev->si_drv2;
 487         if (ce == NULL)
 488                 return (ENODEV);
 489
 490         SND_CLONE_ASSERT(ce->parent != NULL, ("NULL parent"));
 491
 492         ce->flags &= ~SND_CLONE_INVOKE;
 493
 494         if (ce->flags & SND_CLONE_BUSY)
 495                 return (EBUSY);
 496
 497         ce->flags |= SND_CLONE_BUSY;
 498
 499         return (0);
 500 }
 501
 502 /*
 503  * snd_clone_release() : Release busy status. Must be called somewhere at
 504  * the end of close() handler, or somewhere after fail open().
 505  */
 506 int
 507 snd_clone_release(struct cdev *dev)
 508 {
 509         struct snd_clone_entry *ce;
 510
 511         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 512
 513         ce = dev->si_drv2;
 514         if (ce == NULL)
 515                 return (ENODEV);
 516
 517         SND_CLONE_ASSERT(ce->parent != NULL, ("NULL parent"));
 518
 519         ce->flags &= ~SND_CLONE_INVOKE;
 520
 521         if (!(ce->flags & SND_CLONE_BUSY))
 522                 return (EBADF);
 523
 524         ce->flags &= ~SND_CLONE_BUSY;
 525         ce->pid = -1;
 526
 527         return (0);
 528 }
 529
 530 /*
 531  * snd_clone_ref/unref() : Garbage collector reference counter. To make
 532  * garbage collector run automatically, the sequence must be something like
 533  * this (both in open() and close() handlers):
 534  *
 535  *  open() - 1) snd_clone_acquire()
 536  *           2) .... check check ... if failed, snd_clone_release()
 537  *           3) Success. Call snd_clone_ref()
 538  *
 539  * close() - 1) .... check check check ....
 540  *           2) Success. snd_clone_release()
 541  *           3) snd_clone_unref() . Garbage collector will run at this point
 542  *              if this is the last referenced object.
 543  */
 544 int
 545 snd_clone_ref(struct cdev *dev)
 546 {
 547         struct snd_clone_entry *ce;
 548         struct snd_clone *c;
 549
 550         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 551
 552         ce = dev->si_drv2;
 553         if (ce == NULL)
 554                 return (0);
 555
 556         c = ce->parent;
 557         SND_CLONE_ASSERT(c != NULL, ("NULL parent"));
 558         SND_CLONE_ASSERT(c->refcount >= 0, ("refcount < 0"));
 559
 560         return (++c->refcount);
 561 }
 562
 563 int
 564 snd_clone_unref(struct cdev *dev)
 565 {
 566         struct snd_clone_entry *ce;
 567         struct snd_clone *c;
 568
 569         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 570
 571         ce = dev->si_drv2;
 572         if (ce == NULL)
 573                 return (0);
 574
 575         c = ce->parent;
 576         SND_CLONE_ASSERT(c != NULL, ("NULL parent"));
 577         SND_CLONE_ASSERT(c->refcount > 0, ("refcount <= 0"));
 578
 579         c->refcount--;
 580
 581         /*
 582          * Run automatic garbage collector, if needed.
 583          */
 584         if ((c->flags & SND_CLONE_GC_UNREF) &&
 585             (!(c->flags & SND_CLONE_GC_LASTREF) ||
 586             (c->refcount == 0 && (c->flags & SND_CLONE_GC_LASTREF))))
 587                 (void)snd_clone_gc(c);
 588
 589         return (c->refcount);
 590 }
 591
 592 void
 593 snd_clone_register(struct snd_clone_entry *ce, struct cdev *dev)
 594 {
 595         SND_CLONE_ASSERT(ce != NULL, ("NULL snd_clone_entry"));
 596         SND_CLONE_ASSERT(dev != NULL, ("NULL dev"));
 597         SND_CLONE_ASSERT(dev->si_drv2 == NULL, ("dev->si_drv2 not NULL"));
 598         SND_CLONE_ASSERT((ce->flags & SND_CLONE_ALLOC) == SND_CLONE_ALLOC,
 599             ("invalid clone alloc flags=0x%08x", ce->flags));
 600         SND_CLONE_ASSERT(ce->devt == NULL, ("ce->devt not NULL"));
 601         SND_CLONE_ASSERT(ce->unit == dev2unit(dev),
 602             ("invalid unit ce->unit=0x%08x dev2unit=0x%08x",
 603             ce->unit, dev2unit(dev)));
 604
 605         SND_CLONE_ASSERT(ce->parent != NULL, ("NULL parent"));
 606
 607         dev->si_drv2 = ce;
 608         ce->devt = dev;
 609         ce->flags &= ~SND_CLONE_ALLOC;
 610         ce->flags |= SND_CLONE_INVOKE;
 611 }
 612
 613 struct snd_clone_entry *
 614 snd_clone_alloc(struct snd_clone *c, struct cdev **dev, int *unit, int tmask)
 615 {
 616         struct snd_clone_entry *ce, *after, *bce, *cce, *nce, *tce;
 617         struct timespec now;
 618         int cunit, allocunit;
 619         pid_t curpid;
 620
 621         SND_CLONE_ASSERT(c != NULL, ("NULL snd_clone"));
 622         SND_CLONE_ASSERT(dev != NULL, ("NULL dev pointer"));
 623         SND_CLONE_ASSERT((c->typemask & tmask) == tmask,
 624             ("invalid tmask: typemask=0x%08x tmask=0x%08x",
 625             c->typemask, tmask));
 626         SND_CLONE_ASSERT(unit != NULL, ("NULL unit pointer"));
 627         SND_CLONE_ASSERT(*unit == -1 || !(*unit & (c->typemask | tmask)),
 628             ("typemask collision: typemask=0x%08x tmask=0x%08x *unit=%d",
 629             c->typemask, tmask, *unit));
 630
 631         if (!(c->flags & SND_CLONE_ENABLE) ||
 632             (*unit != -1 && *unit > c->maxunit))
 633                 return (NULL);
 634
 635         ce = NULL;
 636         after = NULL;
 637         bce = NULL;     /* "b"usy candidate */
 638         cce = NULL;     /* "c"urthread/proc candidate */
 639         nce = NULL;     /* "n"ull, totally unbusy candidate */
 640         tce = NULL;     /* Last "t"ry candidate */
 641         cunit = 0;
 642         allocunit = (*unit == -1) ? 0 : *unit;
 643         curpid = curthread->td_proc->p_pid;
 644
 645         snd_timestamp(&now);
 646
 647         TAILQ_FOREACH(ce, &c->head, link) {
 648                 /*
 649                  * Sort incrementally according to device type.
 650                  */
 651                 if (tmask > (ce->unit & c->typemask)) {
 652                         if (cunit == 0)
 653                                 after = ce;
 654                         continue;
 655                 } else if (tmask < (ce->unit & c->typemask))
 656                         break;
 657
 658                 /*
 659                  * Shoot.. this is where the grumpiness begin. Just
 660                  * return immediately.
 661                  */
 662                 if (*unit != -1 && *unit == (ce->unit & ~tmask))
 663                         goto snd_clone_alloc_out;
 664
 665                 cunit++;
 666                 /*
 667                  * Simmilar device type. Sort incrementally according
 668                  * to allocation unit. While here, look for free slot
 669                  * and possible collision for new / future allocation.
 670                  */
 671                 if (*unit == -1 && (ce->unit & ~tmask) == allocunit)
 672                         allocunit++;
 673                 if ((ce->unit & ~tmask) < allocunit)
 674                         after = ce;
 675                 /*
 676                  * Clone logic:
 677                  *   1. Look for non busy, but keep track of the best
 678                  *      possible busy cdev.
 679                  *   2. Look for the best (oldest referenced) entry that is
 680                  *      in a same process / thread.
 681                  *   3. Look for the best (oldest referenced), absolute free
 682                  *      entry.
 683                  *   4. Lastly, look for the best (oldest referenced)
 684                  *      any entries that doesn't fit with anything above.
 685                  */
 686                 if (ce->flags & SND_CLONE_BUSY) {
 687                         if (ce->devt != NULL && (bce == NULL ||
 688                             timespeccmp(&ce->tsp, &bce->tsp, <)))
 689                                 bce = ce;
 690                         continue;
 691                 }
 692                 if (ce->pid == curpid &&
 693                     (cce == NULL || timespeccmp(&ce->tsp, &cce->tsp, <)))
 694                         cce = ce;
 695                 else if (!(ce->flags & SND_CLONE_INVOKE) &&
 696                     (nce == NULL || timespeccmp(&ce->tsp, &nce->tsp, <)))
 697                         nce = ce;
 698                 else if (tce == NULL || timespeccmp(&ce->tsp, &tce->tsp, <))
 699                         tce = ce;
 700         }
 701         if (*unit != -1)
 702                 goto snd_clone_alloc_new;
 703         else if (cce != NULL) {
 704                 /* Same proc entry found, go for it */
 705                 ce = cce;
 706                 goto snd_clone_alloc_out;
 707         } else if (nce != NULL) {
 708                 /*
 709                  * Next, try absolute free entry. If the calculated
 710                  * allocunit is smaller, create new entry instead.
 711                  */
 712                 if (allocunit < (nce->unit & ~tmask))
 713                         goto snd_clone_alloc_new;
 714                 ce = nce;
 715                 goto snd_clone_alloc_out;
 716         } else if (allocunit > c->maxunit) {
 717                 /*
 718                  * Maximum allowable unit reached. Try returning any
 719                  * available cdev and hope for the best. If the lookup is
 720                  * done for things like stat(), mtime() etc. , things should
 721                  * be ok. Otherwise, open() handler should do further checks
 722                  * and decide whether to return correct error code or not.
 723                  */
 724                 if (tce != NULL) {
 725                         ce = tce;
 726                         goto snd_clone_alloc_out;
 727                 } else if (bce != NULL) {
 728                         ce = bce;
 729                         goto snd_clone_alloc_out;
 730                 }
 731                 return (NULL);
 732         }
 733
 734 snd_clone_alloc_new:
 735         /*
 736          * No free entries found, and we still haven't reached maximum
 737          * allowable units. Allocate, setup a minimal unique entry with busy
 738          * status so nobody will monkey on this new entry. Unit magic is set
 739          * right here to avoid collision with other contesting handler.
 740          * The caller must be carefull here to maintain its own
 741          * synchronization, as long as it will not conflict with malloc(9)
 742          * operations.
 743          *
 744          * That said, go figure.
 745          */
 746         ce = malloc(sizeof(*ce), M_DEVBUF,
 747             ((c->flags & SND_CLONE_WAITOK) ? M_WAITOK : M_NOWAIT) | M_ZERO);
 748         if (ce == NULL) {
 749                 if (*unit != -1)
 750                         return (NULL);
 751                 /*
 752                  * We're being dense, ignorance is bliss,
 753                  * Super Regulatory Measure (TM).. TRY AGAIN!
 754                  */
 755                 if (nce != NULL) {
 756                         ce = nce;
 757                         goto snd_clone_alloc_out;
 758                 } else if (tce != NULL) {
 759                         ce = tce;
 760                         goto snd_clone_alloc_out;
 761                 } else if (bce != NULL) {
 762                         ce = bce;
 763                         goto snd_clone_alloc_out;
 764                 }
 765                 return (NULL);
 766         }
 767         /* Setup new entry */
 768         ce->parent = c;
 769         ce->unit = tmask | allocunit;
 770         ce->pid = curpid;
 771         ce->tsp = now;
 772         ce->flags |= SND_CLONE_ALLOC;
 773         if (after != NULL) {
 774                 TAILQ_INSERT_AFTER(&c->head, after, ce, link);
 775         } else {
 776                 TAILQ_INSERT_HEAD(&c->head, ce, link);
 777         }
 778         c->size++;
 779         c->tsp = now;
 780         /*
 781          * Save new allocation unit for caller which will be used
 782          * by make_dev().
 783          */
 784         *unit = allocunit;
 785
 786         return (ce);
 787
 788 snd_clone_alloc_out:
 789         /*
 790          * Set, mark, timestamp the entry if this is a truly free entry.
 791          * Leave busy entry alone.
 792          */
 793         if (!(ce->flags & SND_CLONE_BUSY)) {
 794                 ce->pid = curpid;
 795                 ce->tsp = now;
 796                 ce->flags |= SND_CLONE_INVOKE;
 797         }
 798         c->tsp = now;
 799         *dev = ce->devt;
 800
 801         return (NULL);
 802 }